这几天看了N多论文研究了下后缀自己主动机。刚開始蛋疼的看着极短的代码和clj的论文硬是看不懂，后来结合其它几篇论文研究了下。总算是明确了一些

推荐文章

看了几篇文章认为还是这篇写的清晰明了，建议看几遍明确怎样建SAM再看了clj的论文。

clj的论文中对性质的研究比較深入

以下是clj论文里推荐的一题，题意:给一个字符串S，令F(x)表示S的全部长度为x的子串中，出现次数的最大值。求F(1)..F(Length(S)) （感谢clj的翻译>_<）

首先按顺序建SAM。一个串的|Right|就是出现次数。

因为父节点的Right集合正好等于子节点Right集合的并集，于是能够拓扑排序从后往前找，然后每次再把子节点的Right加到pre节点上就可以。这里拓扑排序使用了类似于计数排序的思想。见代码

#include
     
      //SAM#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int N=250005<<1;int last,tot,son[N][26],pre[N],step[N],cnt[N],Q[N],g[N],f[N];char s[N];void ins(int x,int m){	int p=last,np=++tot;	step[np]=m,last=np,g[np]++;	for(;!son[p][x] && p!=-1;p=pre[p])	son[p][x]=np;	if(p==-1)	return;	else{		int q=son[p][x];		if(step[q]==step[p]+1)	pre[np]=q;		else{			step[++tot]=step[p]+1;			int nq=tot;			memcpy(son[nq],son[q],sizeof(son[q]));			pre[nq]=pre[q];			pre[q]=pre[np]=nq;			for(;son[p][x]==q && p!=-1;p=pre[p])	son[p][x]=nq;			}	}}int main(){	pre[0]=-1;	scanf("%s",s);	int l=strlen(s);	for(int i=0;i
          
           =1;--i) printf("%d\n",step[Q[i]]); for(int i=tot;i>=1;--i) f[step[Q[i]]]=max(f[step[Q[i]]],g[Q[i]]),g[pre[Q[i]]]+=g[Q[i]]; for(int i=1;i<=l;++i) printf("%d\n",f[i]); return 0;}