题目概述

LOJ3049

解题报告

把串反过来，那么 $B$ 是 $A$ 前缀就变成 $B$ 是 $A$ 后缀，也就是 $B$ 是 $A$ 在SAM上的parent树祖先，或者B和A在SAM同一个节点上，但A比B长。

一个基础的想法：首先先将parent树从上往下连边权为 $0$ 的边，然后找到每一个支配条件 $A_x$ 和 $B_y$ 对应的SAM节点 $a,b$，然后连一条 $a\to b$ 的边权为 $A_x$ 长度的边，最后跑拓扑，如果有环说明可以接成无穷，否则求出最长路径。

但是由于加粗的那一句话，简单的连 $a\to b$ 的边是有问题的，因为有可能同一个节点连向了同一个节点，但事实上由于长度更长而没有产生环。

那么我们把SAM上的一个点 $x$ 改成一条链，从属于 $x$ 中的长度最短的 $A_i$ 一直连向长度最长的 $A_i$ ，最后连向 $x$（表示 $x$ 这个点代表的最长子串），然后 $x$ 连向 $x$ 在parent树中儿子节点的链的第一个节点。

每次对于一个支配条件 $A_x$ 和 $B_y$ ，找到 $B_y$ 对应SAM节点那条链中第一个大于等于 $B_y$ 长度的点，将 $A_x$ 连向这个点就可以规避长度问题。

示例程序

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200000,maxt=maxn<<1,maxm=maxt+maxn,maxe=maxt+maxn+maxn,LOG=19;

int te,len,Q,n,la[maxn+5],ra[maxn+5],m,lb[maxn+5],rb[maxn+5];
char s[maxn+5];int ID[maxn+5];
int pl,ro,son[maxt+5][26],MAX[maxt+5],fai[maxt+5],ST[maxt+5][LOG+1];
int ha[maxn+5],SA[maxt+5];
int who[maxn+5],A[maxn+5],B[maxn+5];
vector<int> e[maxt+5];
int E,lnk[maxm+5],nxt[maxe+5],to[maxe+5],w[maxe+5],D[maxm+5];
int que[maxm+5];
LL dis[maxm+5],ans;

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
int reads(char *s){
    int len=0;char ch=readc();
    while (!islower(ch)) {if (ch==EOF) return EOF;ch=readc();}
    while (islower(ch)) s[++len]=ch,ch=readc();
    s[len+1]=0;return len;
}
int newnode() {pl++;for (int i=0;i<26;i++) son[pl][i]=0;return pl;}
int Extend(int p,int c,int id){
    int np=newnode();MAX[np]=MAX[p]+1;ID[id]=np;
    while (p && !son[p][c]) son[p][c]=np,p=fai[p];
    if (!p) {fai[np]=ro;return np;}
    int q=son[p][c];if (MAX[p]+1==MAX[q]) {fai[np]=q;return np;}
    int nq=newnode();MAX[nq]=MAX[p]+1;
    for (int i=0;i<26;i++) son[nq][i]=son[q][i];
    fai[nq]=fai[q];fai[q]=fai[np]=nq;
    while (p && son[p][c]==q) son[p][c]=nq,p=fai[p];
    return np;
}
int Find(int L,int R){
    int len=R-L+1,x=ID[R];
    for (int j=LOG;~j;j--)
        if (ST[x][j] && MAX[ST[x][j]]>=len) x=ST[x][j];
    return x;
}
inline void Add(int x,int y,int z) {to[++E]=y;D[y]++;w[E]=z;nxt[E]=lnk[x];lnk[x]=E;}
inline bool cmp(const int &i,const int &j) {return ra[i]-la[i]<ra[j]-la[j];}
int main(){
    for (readi(te);te;te--){
        len=reads(s);reverse(s+1,s+1+len);
        readi(n);
        for (int i=1;i<=n;i++)
            readi(ra[i]),readi(la[i]),
            la[i]=len-la[i]+1,ra[i]=len-ra[i]+1;
        readi(m);
        for (int i=1;i<=m;i++)
            readi(rb[i]),readi(lb[i]),
            lb[i]=len-lb[i]+1,rb[i]=len-rb[i]+1;
        pl=0;ro=newnode();
        for (int i=1,p=ro;i<=len;i++) p=Extend(p,s[i]-'a',i);
        for (int i=0;i<=len;i++) ha[i]=0;
        for (int i=1;i<=pl;i++) ha[MAX[i]]++;
        for (int i=1;i<=len;i++) ha[i]+=ha[i-1];
        for (int i=1;i<=pl;i++) SA[ha[MAX[i]]--]=i;
        for (int i=1,x=SA[i];i<=pl;i++,x=SA[i]){
            ST[x][0]=fai[x];
            for (int j=1;j<=LOG;j++) ST[x][j]=ST[ST[x][j-1]][j-1];
        }
        for (int i=1;i<=n;i++) who[i]=i;
        sort(who+1,who+1+n,cmp);
        for (int i=1;i<=n;i++) A[i]=Find(la[i],ra[i]);
        for (int i=1;i<=m;i++) B[i]=Find(lb[i],rb[i]);
        for (int i=1;i<=pl;i++) e[i].clear();
        E=0;for (int i=1;i<=pl+n;i++) lnk[i]=D[i]=dis[i]=0;
        for (int k=1,i=who[k];k<=n;k++,i=who[k]){
            int x=A[i],lst=(e[x].empty()?0:e[x].back());
            if (lst) Add(lst,i,0);e[x].push_back(i);
        }
//        for (int i=1;i<=pl;i++){
//            printf("[%d]\n",i+n);
//            for (auto x:e[i]) printf("%d ",x);puts("");
//        }
        for (int i=1;i<=pl;i++){
            if (!e[i].empty()) Add(e[i].back(),i+n,0);
            e[i].push_back(i+n);
            if (fai[i]) Add(fai[i]+n,e[i].front(),0);
        }
        readi(Q);
        for (int i=1;i<=Q;i++){
            int x,y;readi(x);readi(y);
            int L=0,R=int(e[B[y]].size())-2;
            for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
                ra[e[B[y]][mid]]-la[e[B[y]][mid]]>=rb[y]-lb[y]?R=mid-1:L=mid+1;
            Add(x,e[B[y]][L],ra[x]-la[x]+1);
        }
        int Head=0,Tail=0;
        for (int i=1;i<=pl+n;i++) if (!D[i]) que[++Tail]=i;
        while (Head!=Tail)
            for (int x=que[++Head],j=lnk[x],u;j;j=nxt[j]){
                u=to[j];dis[u]=max(dis[u],dis[x]+w[j]);
                if (!(--D[u])) que[++Tail]=u;
            }
        for (int i=1;i<=pl+n;i++) if (D[i]) goto GG;
        ans=0;
        for (int i=1;i<=n;i++) ans=max(ans,dis[i]+ra[i]-la[i]+1);
        printf("%lld\n",ans);
        continue;GG:puts("-1");
    }
    return 0;
}