[十二省联考2019]字符串问题

雨点打透心脏的1/2处 2022-01-09 07:43 180阅读 0赞

## [ 传送门 ][Link 1] ##

## **Description**  ##

> 现有一个字符串 \\(S\\)。
> 
> 从中划出 \\(n\_a\\)个子串作为 \\(A\\) 类串，第 \\(i\\)个（\\(1 \\leqslant i \\leqslant n\_a\\)）为 \\(A\_i = S(la\_i, ra\_i)\\)。
> 
> 类似地，划出 \\(n\_b\\)个子串作为 \\(B\\) 类串，第 \\(i\\)个（\\(1 \\leqslant i \\leqslant n\_b\\)）为 \\(B\_i = S(lb\_i, rb\_i)\\)。
> 
> 给定 \\(m\\) 组支配关系，每组支配关系 \\((x, y)\\) 描述了第 \\(x\\) 个 \\(A\\)类串**支配**. 第 \\(y\\)个 \\(B\\) 类串。
> 
> 求一个**长度最大**的目标串 \\(T = t\_1+t\_2+· · ·+t\_k\\)（\\(k⩾0\\)）满足：
> 
>  *  分割中的每个串 \\(t\_i\\) 均为\\(A\\)类串
>  *  对于分割中所有相邻的串 \\(t\_i\\), \\(t\_\{i+1\}\\)（\\(1 \\leqslant i < k\\)），都有存在一个\\(t\_i\\)支配的 \\(B\\) 类串，使得该 \\(B\\) 类串为 \\(t\_\{i+1\}\\)的前缀。
> 
> 输出这个最大的长度。如果存在无穷大的长度，则输出\\(-1\\)

## **Description**  ##

> 题意就是：我们要找到每个\\(A\\)类串是否能作为另一个串的后继，连边，跑最长路，如果有环就输出\\(-1\\)
> 
> 重点在于如何优化连边：
> 
> 1.  线段树优化连边？其实是可以的
> 2.  前后缀优化连边？想太多
> 3.  \*后缀树优化连边？就它啦
> 
> 我们的连边方式其实上是，\\(A\\)类串向其能够支配的\\(B\\)类串连边，然后\\(B\\)类串再向能作为其前缀的\\(A\\)类串连边，显然，我们在\\(B\\rightarrow A\\)上进行优化
> 
> 优化\\(1\\)：考虑到较小的\\(B\\)类串可以向较大的\\(B\\)类串连边，就可省去部分\\(B\\rightarrow A\\)的边
> 
> 把前缀换成后缀，也就是处理原串的反串，建出它的后缀自动机
> 
> 然后我们就能得到一棵\\(parent\\)树，这棵树上每个节点所带表的串是其子树内其它串的后缀
> 
> 那么也就是原串中的前缀
> 
> 首先，我们对于每个\\(A\\)、\\(B\\)类串，找到它在后缀自动机上的位置，显然有可能有多个串位于同一个位置，怎么找位置呢，倍增就行啦
> 
> 优化\\(2\\)：对于\\(parent\\)树上的父节点，向其子节点连边
> 
> 但是有可能有多个串处在同一个节点上，把点按照大小排序，相同长度的\\(A\\)类串位于\\(B\\)类串之后，然后每个\\(B\\)串只向长度大于等于它的且小于下一个\\(B\\)串的\\(A\\)类串连边，只需最后一个\\(B\\)类串向子节点的第一个\\(B\\)串连边即可。

## **Code ** ##

#include<bits/stdc++.h> #define ll long long #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)>(b)?(b):(a)) #define reg register inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } const int MN=2e5+5; char s[MN]; int na,nb; struct Str{int l,r;}a[MN<<1]; int last,cnt,len,step[MN<<1],c[MN<<1][27],fail[MN<<1][22],pos[MN]; struct edge{int to,nex;}sam[MN<<1],e[MN<<4]; int shr[MN<<1],hr[MN<<1],sen,en,rdu[MN<<1]; void ins(int x,int y,int *h,int &_,edge *E){E[++_]=(edge){y,h[x]};h[x]=_;} void Ins(int x,int y){ins(x,y,hr,en,e);++rdu[y];} void Insert(int x) { int p=last,np=++cnt;step[np]=step[p]+1; pos[len-step[np]+1]=np; for(;p&&!c[p][x];p=fail[p][0]) c[p][x]=np; if(!p) fail[np][0]=1; else { int q=c[p][x]; if(step[q]==step[p]+1) fail[np][0]=q; else { int nq=++cnt;step[nq]=step[p]+1; memcpy(c[nq],c[q],sizeof c[q]); fail[nq][0]=fail[q][0];fail[q][0]=fail[np][0]=nq; for(;c[p][x]==q;p=fail[p][0])c[p][x]=nq; } } last=np; } int get(int x,int Len) { reg int i,o=pos[x]; for(i=20;~i;--i)if(step[fail[o][i]]>=Len) o=fail[o][i]; return o; } std::vector<int> Set[MN<<1]; void dfs(int x,int fa,int las) { reg int i; for(i=0;i<Set[x].size();++i) if(Set[x][i]<=na) {if(~las) Ins(las,Set[x][i]);} else {if(~las) Ins(las,Set[x][i]);las=Set[x][i];} for(i=shr[x];i;i=sam[i].nex)if(sam[i].to!=fa) dfs(sam[i].to,x,las); } #define ln(x) (a[x].r-a[x].l+1) bool cmp(int i,int j){return ln(i)<ln(j)||(ln(i)==ln(j)&&i>j);} void pre_work() { reg int i,j; for(i=1;i<=cnt;++i) Set[i].clear(); for(i=2;i<=cnt;++i) ins(fail[i][0],i,shr,sen,sam); for(i=1;i<=20;++i) for(j=1;j<=cnt;++j) fail[j][i]=fail[fail[j][i-1]][i-1]; for(i=1;i<=na+nb;++i) Set[get(a[i].l,ln(i))].push_back(i); for(i=1;i<=cnt;++i) std::sort(Set[i].begin(),Set[i].end(),cmp); dfs(1,0,-1); } int visnum; ll f[MN<<2]; std::queue<int> q; void topo() { reg int i;visnum=0; memset(f,0,sizeof f); for(i=1;i<=na+nb;++i) if(!rdu[i]) q.push(i); while(!q.empty()) { int u=q.front();q.pop(); if(u<=na) ++visnum,f[u]+=ln(u); for(i=hr[u];i;i=e[i].nex) { f[e[i].to]=max(f[e[i].to],f[u]); if(!--rdu[e[i].to]) q.push(e[i].to); } } } void init() { memset(fail,0,sizeof fail); last=1;cnt=1;sen=en=0; memset(rdu,0,sizeof rdu); memset(shr,0,sizeof shr); memset(hr,0,sizeof hr); memset(c,0,sizeof c); } int main() { reg int T=read(),i,x; while(T--) { init(); scanf("%s",s+1);len=strlen(s+1); for(i=len;i;--i) Insert(s[i]-'a'); na=read(); for(i=1;i<=na;++i) a[i].l=read(),a[i].r=read(); nb=read(); for(i=1+na;i<=na+nb;++i) a[i].l=read(),a[i].r=read(); pre_work(); i=read(); while(i--) x=read(),Ins(x,read()+na); topo(); if(visnum<na) puts("-1"); else { reg ll ans=0; for(i=1;i<=na;++i) ans=max(ans,f[i]); printf("%lld\n",ans); } } return 0; }

--------------------

Blog来自**PaperCloud**，未经允许，请勿转载，TKS！

转载于:https://www.cnblogs.com/PaperCloud/p/10689702.html

[Link 1]: https://loj.ac/problem/3049