就用spoj1812的代码做模版吧。。。
#include<bits/stdc++.h> #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const int maxn=1000100; const int INF=1e9+10; struct SAM { int ch[maxn][26]; int pre[maxn],step[maxn]; int last,tot; int Min[maxn],Max[maxn]; void init() { last=tot=0; memset(ch[0],-1,sizeof(ch[0])); pre[0]=-1;step[0]=0; Min[0]=Max[0]=0; } void add(int c) { c-='a'; int p=last,np=++tot; step[np]=step[p]+1; memset(ch[np],-1,sizeof(ch[np])); Min[np]=Max[np]=step[np]; while(~p&&ch[p][c]==-1) ch[p][c]=np,p=pre[p]; if(p==-1) pre[np]=0; else{ int q=ch[p][c]; if(step[q]!=step[p]+1){ int nq=++tot; memcpy(ch[nq],ch[q],sizeof(ch[q])); step[nq]=step[p]+1; Min[nq]=Max[nq]=step[nq]; pre[nq]=pre[q]; pre[q]=pre[np]=nq; while(~p&&ch[p][c]==q) ch[p][c]=nq,p=pre[p]; } else pre[np]=q; } last=np; } void find(char *s) { int len=strlen(s); int u=0; int tmp=0; REP(i,0,tot) Max[i]=0; REP(i,0,len-1){ int c=s[i]-'a'; if(~ch[u][c]) tmp++,u=ch[u][c]; else{ while(~u&&ch[u][c]==-1) u=pre[u]; if(~u) tmp=step[u]+1,u=ch[u][c]; else tmp=0,u=0; } Max[u]=max(Max[u],tmp); } for(int i=tot;i>=1;i--) Max[pre[i]]=max(Max[pre[i]],Max[i]); REP(i,0,tot) Min[i]=min(Min[i],Max[i]); } int calc() { int res=0; REP(i,0,tot) res=max(res,Min[i]); return res; } };SAM A; char s[maxn]; int len; int main() { freopen("in.txt","r",stdin); scanf("%s",s);len=strlen(s); A.init(); REP(i,0,len-1) A.add(s[i]); while(~scanf("%s",s)) A.find(s); printf("%d ",A.calc()); return 0; }
这里和AC自动机的fail指针不一样的是这个比AC自动机具有拓扑关系，是纯粹的DAG，更像回文树，因此匹配更新的时候就不要像AC自动机那样匹配到一个就找沿着fail指针往回走了，因为这样在SAM中是n^2的复杂度，但是可以像回文树计算cnt一样处理，匹配完之后逆序遍历一遍，用每个点更新它的pre结点。
下面是bzoj2555，LCT维护后缀自动机。
#include<bits/stdc++.h> #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const int maxn=3200100; const int INF=1e9+10; char s[maxn]; int len; char op[20]; int Q; struct LCT { int pre[maxn],ch[maxn][2],rev[maxn]; int val[maxn],add[maxn]; void init() { MS0(pre);MS0(ch);MS0(rev);MS0(add); MS0(val); } void update_add(int x,int w) { if(!x) return; val[x]+=w; add[x]+=w; } void update_rev(int x) { if(!x) return; swap(ch[x][0],ch[x][1]); rev[x]^=1; } void down(int x) { if(add[x]){ update_add(ch[x][0],add[x]); update_add(ch[x][1],add[x]); add[x]=0; } if(rev[x]){ update_rev(ch[x][0]); update_rev(ch[x][1]); rev[x]=0; } } bool isroot(int x) { return ch[pre[x]][0]!=x&&ch[pre[x]][1]!=x; } void up(int x) { } void P(int x) { if(!isroot(x)) P(pre[x]); down(x); } void rot(int x,int kind) { int y=pre[x]; ch[y][kind^1]=ch[x][kind]; pre[ch[x][kind]]=y; if(!isroot(y)) ch[pre[y]][ch[pre[y]][1]==y]=x; pre[x]=pre[y]; ch[x][kind]=y; pre[y]=x; up(y); } void splay(int x) { P(x); while(!isroot(x)){ if(isroot(pre[x])) rot(x,ch[pre[x]][0]==x); else{ int y=pre[x],z=pre[y]; int kind=ch[y][0]==x,one=0; if(ch[y][0]==x&&ch[z][0]==y) one=1; if(ch[y][1]==x&&ch[z][1]==y) one=1; if(one) rot(y,kind),rot(x,kind); else rot(x,kind),rot(x,kind^1); } } up(x); } int access(int x) { int t=0; while(x){ splay(x); ch[x][1]=t;t=x;x=pre[x]; up(t); } return t; } void makeroot(int x) { access(x);splay(x);update_rev(x); } void ADD(int x,int y,int w) { makeroot(x);access(y);splay(y); update_add(y,w); } void cut(int x,int y) { makeroot(x);access(y);splay(y);ch[y][0]=pre[x]=0;up(y); ADD(y,1,-val[x]); } void link(int x,int y) { makeroot(x);pre[x]=y;up(y); ADD(y,1,val[x]); } int query(int x) { splay(x); return val[x]; } };LCT lct; struct SAM { int ch[maxn][26]; int pre[maxn],step[maxn]; int last,tot; int newnode(int k) { ++tot; step[tot]=k; MS0(ch[tot]); pre[tot]=0; return tot; } void init() { tot=0; last=newnode(0); lct.init(); } void add(int c) { c-='A'; int p=last,np=newnode(step[p]+1); lct.val[np]=1; while(p&&ch[p][c]==0) ch[p][c]=np,p=pre[p]; if(p==0) pre[np]=1,lct.link(np,1); else{ int q=ch[p][c]; if(step[q]!=step[p]+1){ int nq=newnode(step[p]+1); memcpy(ch[nq],ch[q],sizeof(ch[q])); lct.cut(q,pre[q]); lct.link(nq,pre[q]); lct.link(q,nq); lct.link(np,nq); pre[nq]=pre[q]; pre[q]=pre[np]=nq; while(p&&ch[p][c]==q) ch[p][c]=nq,p=pre[p]; } else pre[np]=q,lct.link(np,q); } last=np; } int find(char *s) { int len=strlen(s); int u=1; REP(i,0,len-1){ int c=s[i]-'A'; if(ch[u][c]) u=ch[u][c]; else return 0; } return lct.query(u); } };SAM sam; void decode(char *s,int mask) { int len=strlen(s); REP(i,0,len-1){ mask=(mask*131+i)%len; swap(s[i],s[mask]); } } int main() { freopen("in.txt","r",stdin); while(~scanf("%d",&Q)){ scanf("%s",s); len=strlen(s); sam.init(); REP(i,0,len-1) sam.add(s[i]); int mask=0; REP(i,1,Q){ scanf("%s%s",op,s); decode(s,mask); if(op[0]=='A'){ len=strlen(s); REP(i,0,len-1) sam.add(s[i]); } else{ int res=sam.find(s); printf("%d ",res); mask^=res; } } } return 0; }