考场以为SA和SAM功能相同。。。
写了SA的80pts线段树优化建图，，，然后就不会了
SA的一大缺点，是只能指出结尾位置，长度不能直接表示。
所以把A串直接放在rk的位置是没法做的。
SAM的parent树，除了可以把前缀统一起来，还有一个好处，
由于本质是子串的出现，节点自带长度限制！，而且从上到下长度递增！
（增加了点的意义，从而不用考虑长度了）
（并且只多了一倍的节点）
然后就可以做了
1.建SAM，挂A串（前缀构图处理）
2.对于限制，倍增找到B的位置，然后往前缀块连边，向新建son节点连边
3.最后SAM内部再连边，连到son[fa[i][0]]的位置
然后愉快topoDP即可
#include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') using namespace std; typedef long long ll; template<class T>il void rd(T &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');} namespace Miracle{ const int N=2e5+5; const int P=2*N+2*N+N; int na,nb,len; char s[N]; struct node{ int nxt,to,w; }e[P+P]; struct seg{ int l,r; }A[N],B[N]; int tmp[N]; bool cmp(int x,int y){ return A[x].r-A[x].l+1<A[y].r-A[y].l+1; } vector<int>to[N]; int pos[N];//pos : suff 's pos int id[N];//A string 's id on parent tree int hd[P],cnt; int du[P]; void add(int x,int y,int w){ e[++cnt].nxt=hd[x]; e[cnt].to=y;e[cnt].w=w; hd[x]=cnt; du[y]++; } int tot;//tot cur struct SAM{ int fa[2*N][20],len[2*N]; int son[2*N]; int ch[2*N][26]; int cnt,nd; vector<int>sl[2*N],sc[2*N]; void init(){ cnt=nd=1; } int ins(int c,int l){ int p=nd;len[nd=++cnt]=l; for(;p&&ch[p][c]==0;p=fa[p][0]) ch[p][c]=nd; if(!p){ fa[nd][0]=1;return nd; } int q=ch[p][c]; if(len[q]==len[p]+1){ fa[nd][0]=q;return nd; } len[++cnt]=len[p]+1; fa[cnt][0]=fa[q][0],fa[q][0]=fa[nd][0]=cnt; for(reg i=0;i<26;++i) ch[cnt][i]=ch[q][i]; for(;p&&ch[p][c]==q;p=fa[p][0]) ch[p][c]=cnt; return nd; } int loc(int p,int l){//typ==0 add ; typ==1 query for(reg j=19;j>=0;--j){ if(fa[p][j]&&len[fa[p][j]]>=l) p=fa[p][j]; } sl[p].push_back(l); sc[p].push_back(++tot); int nc=++tot;add(tot-1,nc,l); if(sc[p].size()==1){ add(p,sc[p][0],0); }else{ add(sc[p][sc[p].size()-2],sc[p][sc[p].size()-1],0); } return nc; } void con(int p,int l,int fr){ for(reg j=19;j>=0;--j){ if(fa[p][j]&&len[fa[p][j]]>=l) p=fa[p][j]; } int nc=lower_bound(sl[p].begin(),sl[p].end(),l)-sl[p].begin(); if(nc!=(int)sl[p].size()){ add(fr,sc[p][nc],0); } if(!son[p]){ son[p]=++tot; } add(fr,son[p],0); } void pre(){//build fa[*][1~18] for(reg j=1;j<=19;++j){ for(reg i=1;i<=cnt;++i){ fa[i][j]=fa[fa[i][j-1]][j-1]; } } } void build(){//build two for(reg i=1;i<=cnt;++i){ if(son[i]) add(i,son[i],0); } for(reg i=2;i<=cnt;++i){ if(!son[fa[i][0]]){ add(fa[i][0],i,0); }else{ add(son[fa[i][0]],i,0); } } } void clear(){ for(reg i=1;i<=cnt;++i){ memset(ch[i],0,sizeof ch[i]); memset(fa[i],0,sizeof fa[i]); len[i]=0;sl[i].clear();sc[i].clear(); son[i]=0; } cnt=nd=1; } }sam; ll f[P]; int q[P],l,r; ll topo(){ l=1;r=0; q[++r]=1; while(l<=r){ int x=q[l++]; for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; f[y]=max(f[y],f[x]+e[i].w); du[y]--; if(!du[y]){ q[++r]=y; } } } for(reg i=1;i<=tot;++i){ if(du[i]!=0) return -1; } ll ret=0; for(reg i=1;i<=tot;++i) ret=max(ret,f[i]); return ret; } void clear(){ for(reg i=1;i<=tot;++i) hd[i]=0,du[i]=0,f[i]=0; for(reg i=1;i<=na;++i) to[i].clear(); tot=0;cnt=0; sam.clear();na=nb=len=0; } int main(){ int t; rd(t); sam.init(); while(t--){ scanf("%s",s+1); len=strlen(s+1); reverse(s+1,s+len+1); rd(na); for(reg i=1;i<=na;++i){ rd(A[i].l);rd(A[i].r); int od=A[i].l; A[i].l=len-A[i].r+1; A[i].r=len-od+1; tmp[i]=i; } sort(tmp+1,tmp+na+1,cmp); rd(nb); for(reg i=1;i<=nb;++i){ rd(B[i].l);rd(B[i].r); int od=B[i].l; B[i].l=len-B[i].r+1; B[i].r=len-od+1; } int m;rd(m); int x,y; for(reg i=1;i<=m;++i){ rd(x);rd(y); to[x].push_back(y); } for(reg i=1;i<=len;++i){ pos[i]=sam.ins(s[i]-'a',i); } sam.pre(); tot=sam.cnt; for(reg i=1;i<=na;++i){ id[tmp[i]]=sam.loc(pos[A[tmp[i]].r],A[tmp[i]].r-A[tmp[i]].l+1); } for(reg i=1;i<=na;++i){ for(reg j=0;j<(int)to[i].size();++j){ int y=to[i][j]; sam.con(pos[B[y].r],B[y].r-B[y].l+1,id[i]); } } sam.build(); ll ans=topo(); printf("%lld\n",ans); clear(); } return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* Date: 2019/4/8 9:58:39 */
一道很好体现了SAM 的parent树结构，和right集合定义的优势的题目
2019.2.28考试 0/1trie优化2-SAT建图也是如此。