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
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)>(b)?(b):(a))#define reg registerinline 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
     
       Set[MN<<1];void dfs(int x,int fa,int las){    reg int i;    for(i=0;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
       
         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
       
      
     
    

---

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