Luogu5284 十二省联考2019字符串问题(后缀树+拓扑排序)
对反串建SAM弄出后缀树,每个b串通过倍增定位其在后缀树上对应的节点,根据其长度将节点拆开。然后每个a串也找到对应的节点,由该节点向表示a串的节点连边,再把所给的边连上跑拓扑排序即可。
#include<bits/stdc++.h> using namespace std; #define ll long long #define N 800010 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int T,n,na,nb,m,son[N][26],fail[N],len[N],id[N],f[N][21],pos[N],cnt,last; char s[N]; struct data{int l,r; }a[N],b[N]; int p[N],degree[N],q[N],val[N],t; ll F[N]; struct data2{int to,nxt; }edge[N<<1]; vector<int> node[N]; void addedge(int x,int y){t++;degree[y]++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;} int newnode(){cnt++;memset(son[cnt],0,sizeof(son[cnt]));fail[cnt]=len[cnt]=0;node[cnt].clear();return cnt;} void ins(int c) { int x=newnode(),p=last;last=x;len[x]=len[p]+1;id[len[x]]=x; while (!son[p][c]&&p) son[p][c]=x,p=fail[p]; if (!p) fail[x]=1; else { int q=son[p][c]; if (len[p]+1==len[q]) fail[x]=q; else { int y=newnode(); len[y]=len[p]+1; memcpy(son[y],son[q],sizeof(son[q])); fail[y]=fail[q],fail[q]=fail[x]=y; while (son[p][c]==q) son[p][c]=y,p=fail[p]; } } } int find(int x,int y) { for (int j=20;~j;j--) if (len[f[x][j]]>=y) x=f[x][j]; return x; } int find2(int x,int y) { if (len[x]<=y) return x; for (int j=20;~j;j--) if (len[f[x][j]]>y) x=f[x][j]; return fail[x]; } bool cmp(int x,int y){return b[x].r<b[y].r;} ll topsort() { int head=0,tail=0; for (int i=1;i<=cnt;i++) { F[i]=val[i]; if (!degree[i]) q[++tail]=i; } while (head<tail) { int x=q[++head]; for (int i=p[x];i;i=edge[i].nxt) { degree[edge[i].to]--; F[edge[i].to]=max(F[edge[i].to],F[x]+val[edge[i].to]); if (!degree[edge[i].to]) q[++tail]=edge[i].to; } } if (tail<cnt) return -1; ll ans=0; for (int i=1;i<=cnt;i++) ans=max(ans,F[i]); return ans; } int main() { #ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif T=read(); while (T--) { scanf("%s",s+1); n=strlen(s+1);cnt=0;last=1;newnode(); for (int i=1;i<=n;i++) ins(s[n-i+1]-'a'); for (int i=1;i<=cnt;i++) f[i][0]=fail[i];f[1][0]=1; for (int j=1;j<21;j++) for (int i=1;i<=cnt;i++) f[i][j]=f[f[i][j-1]][j-1]; na=read(); for (int i=1;i<=na;i++) { a[i].l=read(),a[i].r=read(); a[i].r=a[i].r-a[i].l+1;a[i].l=n-a[i].l+1; } nb=read(); for (int i=1;i<=nb;i++) { b[i].l=read(),b[i].r=read(); b[i].r=b[i].r-b[i].l+1;b[i].l=n-b[i].l+1; int x=find(id[b[i].l],b[i].r); node[x].push_back(i); } for (int i=1;i<=cnt;i++) if (!node[i].empty()) { sort(node[i].begin(),node[i].end(),cmp); int last=fail[i]; for (int j=0;j<node[i].size();) { int x=node[i][j]; if (b[x].r==len[i]) { for (;j<node[i].size();j++) pos[node[i][j]]=i; break; } len[newnode()]=b[x].r;fail[cnt]=last;last=cnt; while (j<node[i].size()&&b[node[i][j]].r==len[cnt]) pos[node[i][j]]=cnt,j++; } fail[i]=last; } for (int i=1;i<=cnt;i++) f[i][0]=fail[i];f[1][0]=1; for (int j=1;j<21;j++) for (int i=1;i<=cnt;i++) f[i][j]=f[f[i][j-1]][j-1]; for (int i=1;i<=cnt+na;i++) F[i]=degree[i]=p[i]=val[i]=0;t=0; for (int i=cnt+1;i<=cnt+na;i++) val[i]=a[i-cnt].r; for (int i=2;i<=cnt;i++) addedge(fail[i],i); for (int i=1;i<=na;i++) addedge(find2(id[a[i].l],a[i].r),cnt+i); m=read(); for (int i=1;i<=m;i++) { int x=read(),y=read(); addedge(cnt+x,pos[y]); } cnt+=na; cout<<topsort()<<endl; } return 0; }