后缀自动机入门
前几天被substr虐了，于是怒而学后缀自动机，结果看了一下午没看懂，囧.......昨天总算是看出点端倪了，发现写起来还是挺短的，起码比后缀数组好写多了~！
原理什么的CLJ大神的课件里讲的已经很细致了，比网上的一些讲的都要透彻，建议初次学习的话还是去看这个。其实一个后缀自动机里的点代表的不光是它自己，还包括所有以它为右端点的字串（曾经的后缀），那么后缀自动机上就可以处理一些字串以及后缀的问题了。它的时空复杂度都是O（n）的，所以可以非常有效地解决一些字符串问题。
这个图可以非常直观地表现后缀自动机的神奇之处：
1.0 NSUBSTR
这个题用后缀自动机做真是一目了然啊，写完才60行......
由于后缀自动机里蕴含了每一个子串（曾经插入某个字符时的后缀），注意一个性质：如果x是一个后缀，那么pre[x]也是一个和x有相同右端点的后缀。然后注意我们保存了每一个点可接受的最大后缀长度（姑且这么称吧，其实是以它为右端点的最大字串长度），那么小于等于这个长度的字串都包含在里面了。那么我们先从rot往后沿着字符串走，把走到的点的计数器设为1：它们是包含以它们为右端点的子串的最大位置，然后从后面最大长度较大的往前更新，更新mx(x)长度的答案，并向前累加计数器。最后别忘了用长度大的答案去更新一下长度小的答案。
注意要用桶排才能不影响O（n）的复杂度。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #define inf 2147483647 7 #define maxn 600000 8 using namespace std; 9 struct node 10 { 11 node *pre,*ch[27]; 12 int mx,v; 13 }sam[maxn],*rot,*now,*r[maxn]; 14 char s[maxn]; 15 int n,m,num; 16 int t[maxn],ans[maxn]; 17 inline void insert(int w) 18 { 19 node *p=now,*np=&sam[++num]; 20 np->mx=p->mx+1; 21 while (p&&p->ch[w]==0) p->ch[w]=np,p=p->pre; 22 if (!p) np->pre=rot; 23 else 24 { 25 node *q=p->ch[w]; 26 if (q->mx==p->mx+1) np->pre=q; 27 else 28 { 29 node *nq=&sam[++num]; 30 *nq=*q; 31 nq->mx=p->mx+1; 32 np->pre=q->pre=nq; 33 while (p&&p->ch[w]==q) p->ch[w]=nq,p=p->pre; 34 } 35 } 36 now=np; 37 } 38 39 int main() 40 { 41 scanf("%s",s); 42 n=strlen(s),m=27; 43 rot=now=&sam[num=1]; 44 for (int i=0;i<n;i++) insert(s[i]-'a'); 45 for (int i=0;i<=n;i++) t[i]=0; 46 for (int i=1;i<=num;i++) t[sam[i].mx]++; 47 for (int i=1;i<=n;i++) t[i]+=t[i-1]; 48 for (int i=num;i>=1;i--) r[t[sam[i].mx]--]=&sam[i]; 49 now=rot; 50 for (int i=0;i<n;i++) (now=now->ch[s[i]-'a'])->v=1; 51 for (int i=num;i>=2;i--) 52 { 53 ans[r[i]->mx]=max(ans[r[i]->mx],r[i]->v); 54 r[i]->pre->v+=r[i]->v; 55 } 56 for (int i=n-1;i>=1;i--) ans[i]=max(ans[i],ans[i+1]); 57 for (int i=1;i<=n;i++) printf("%d\n",ans[i]); 58 return 0; 59 } 60 61 62
1.1 LCS
用后缀自动机做字符串最大匹配问题，其实和AC自动机的原理差不多，用一个建自动机，另一个往上配，失配了再往前找，退一步求其次，然后如果重新配上了，那么计数器变为新的起始节点的mx+1。用计数器去更新答案。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #define inf 2147483647 7 #define maxn 600000 8 using namespace std; 9 struct node 10 { 11 node *pre,*ch[27]; 12 int mx,v; 13 }sam[maxn],*rot,*now; 14 char s[maxn],t[maxn]; 15 int n,m,num,ans; 16 inline void insert(int w) 17 { 18 node *p=now,*np=&sam[++num]; 19 np->mx=p->mx+1; 20 while (p&&p->ch[w]==0) p->ch[w]=np,p=p->pre; 21 if (!p) np->pre=rot; 22 else 23 { 24 node *q=p->ch[w]; 25 if (q->mx==p->mx+1) np->pre=q; 26 else 27 { 28 node *nq=&sam[++num]; 29 *nq=*q; 30 nq->mx=p->mx+1; 31 np->pre=q->pre=nq; 32 while (p&&p->ch[w]==q) p->ch[w]=nq,p=p->pre; 33 } 34 } 35 now=np; 36 } 37 38 int main() 39 { 40 scanf("%s%s",s,t); 41 n=strlen(s); 42 now=rot=&sam[num=1]; 43 for (int i=0;i<n;i++) insert(s[i]-'a'); 44 //for (int i=1;i<=n;i++) cout<<i<<' '<<sam[i].pre-sam<<' '<<sam[i].mx<<endl; 45 m=strlen(t); 46 node *p=rot; 47 int tmp=0; 48 for (int i=0;i<m;i++) 49 { 50 if (p->ch[t[i]-'a']) p=p->ch[t[i]-'a'],tmp++; 51 else 52 { 53 while (p&&p->ch[t[i]-'a']==0) p=p->pre;//失配了往前找 54 if (p) tmp=p->mx+1,p=p->ch[t[i]-'a'];//能匹配上的个数是找到节点的最大串长mx+1 55 else 56 p=rot,tmp=0; 57 } 58 if (tmp>ans) ans=tmp; 59 } 60 printf("%d\n",ans); 61 return 0; 62 }
1.2 LCS2
和上一个原理一样，只不过是用另外的每一个串在自动机上跑一次，不断地更新这一次在每一个状态上的最大匹配数，最后在每个状态上的n-1个匹配数和这个点的mx上取一个最小值表示这个状态的匹配数，用它去更新答案。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #define inf 2147483647 7 #define maxn 300000 8 using namespace std; 9 struct node 10 { 11 node *pre,*ch[30]; 12 int mx,v[20]; 13 }sam[maxn],*rot,*now; 14 char s[maxn]; 15 int g[maxn]; 16 int n,m,num,ans,r; 17 void insert(int w) 18 { 19 node *p=now,*np=&sam[++num]; 20 np->mx=p->mx+1; 21 while (p&&p->ch[w]==0) p->ch[w]=np,p=p->pre; 22 if (!p) np->pre=rot; 23 else 24 { 25 node *q=p->ch[w]; 26 if (q->mx==p->mx+1) np->pre=q; 27 else 28 { 29 node *nq=&sam[++num]; 30 *nq=*q; 31 nq->mx=p->mx+1; 32 np->pre=q->pre=nq; 33 while (p&&p->ch[w]==q) p->ch[w]=nq,p=p->pre; 34 } 35 } 36 now=np; 37 } 38 39 int main() 40 { 41 scanf("%s",s); 42 n=strlen(s); 43 rot=now=&sam[num=1]; 44 for (int i=0;i<n;i++) insert(s[i]-'a'); 45 r=0; 46 while (scanf("%s",s)!=EOF) 47 { 48 r++; 49 int m=strlen(s); 50 int tmp=0; 51 node *p=rot; 52 for (int i=0;i<m;i++) 53 { 54 int w=s[i]-'a'; 55 if (p->ch[w]) 56 { 57 ++tmp,p=p->ch[w]; 58 if (p) p->v[r]=max(p->v[r],tmp); 59 } 60 else 61 { 62 while (p&&p->ch[w]==0) p=p->pre; 63 if (p) 64 { 65 tmp=p->mx+1,p=p->ch[w]; 66 p->v[r]=max(p->v[r],tmp); 67 } 68 else tmp=0,p=rot; 69 } 70 } 71 for (int i=num;i>=1;i--) 72 { 73 p=&sam[i]; 74 if (p->pre) p->pre->v[r]=max(p->v[r],p->pre->v[r]); 75 } 76 } 77 ans=0; 78 for (int i=1;i<=num;i++) 79 { 80 g[i]=sam[i].mx; 81 for (int j=1;j<=r;j++) 82 g[i]=min(g[i],sam[i].v[j]); 83 ans=max(ans,g[i]); 84 } 85 printf("%d\n",ans); 86 return 0; 87 } 88
1.3 SUBLEX
要求用给定串建立字母树，我们可以看到，如果我们沿着自动机走，是可以像字母树一样走到每一个串的，于是我们只需要维护一下每个节点的size域就可以找到第k大的串了。但是此题这么做貌似时间上还需要优化，于是可以把每个点的26个转移中为空的转移去掉，把有用的转移离散出来，这样就可以很迅速地达到相应的字串了。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #define inf 2147483647 7 #define maxn 300000 8 using namespace std; 9 struct node 10 { 11 node *pre,*ch[27],*d[27]; 12 int mx,size,sum; 13 char ac[27]; 14 }sam[maxn],*rot,*now,*r[maxn]; 15 char s[maxn]; 16 int t[maxn]; 17 int n,m,num,ans; 18 inline void insert(int w) 19 { 20 node *p=now,*np=&sam[++num]; 21 np->mx=p->mx+1; np->size=1; 22 while (p&&p->ch[w]==0) p->ch[w]=np,p=p->pre; 23 if (!p) np->pre=rot; 24 else 25 { 26 node *q=p->ch[w]; 27 if (q->mx==p->mx+1) np->pre=q; 28 else 29 { 30 node *nq=&sam[++num]; 31 *nq=*q; 32 nq->size=1; 33 nq->mx=p->mx+1; 34 np->pre=q->pre=nq; 35 while (p&&p->ch[w]==q) p->ch[w]=nq,p=p->pre; 36 } 37 } 38 now=np; 39 } 40 41 void find(node *now,int k) 42 { 43 if (now->sum==0||k==0) return; 44 int tmp=0; 45 for (int i=1;i<=(now->sum);i++) 46 { 47 node *p=now->d[i]; 48 tmp=i; 49 if (k>p->size) 50 k-=p->size; 51 else 52 { 53 k--; 54 break; 55 } 56 } 57 printf("%c",now->ac[tmp]); 58 find(now->d[tmp],k); 59 } 60 61 void add(node *k,int j,int tot) 62 { 63 k->size+=k->ch[j]->size; 64 k->d[tot]=k->ch[j]; 65 k->ac[tot]=j+'a'; 66 } 67 68 int main() 69 { 70 scanf("%s",s); 71 n=strlen(s); 72 now=rot=&sam[num=1]; 73 for (int i=0;i<n;i++) insert(s[i]-'a'); 74 for (int i=0;i<=n;i++) t[i]=0; 75 for (int i=1;i<=num;i++) t[sam[i].mx]++; 76 for (int i=1;i<=n;i++) t[i]+=t[i-1]; 77 for (int i=num;i>=1;i--) r[t[sam[i].mx]--]=&sam[i]; 78 for (int i=num;i>=1;i--) 79 { 80 node *k=r[i];k->sum=0; 81 for (int j=0;j<26;j++) 82 if (k->ch[j]) 83 add(k,j,++k->sum); 84 } 85 scanf("%d",&m); 86 int y; 87 for (int i=1;i<=m;i++) 88 { 89 scanf("%d",&y); 90 find(rot,y); 91 printf("\n"); 92 } 93 return 0; 94 }
最后，后缀自动机虽然短，但是处理问题的时候还需要对它的性质理解的足够深入，光会敲模板一点用也没有，以后还需多加体会。
转载于:https://www.cnblogs.com/zig-zag/archive/2013/04/07/3003337.html