這幾天看了N多論文研究了下后綴自己主動機。剛開始蛋疼的看著極短的代碼和clj的論文硬是看不懂，后來結合其它幾篇論文研究了下?？偹闶敲鞔_了一些

推薦文章http://blog.sina.com.cn/s/blog_70811e1a01014dkz.html

看了幾篇文章認為還是這篇寫的清晰明了，建議看幾遍明確怎樣建SAM再看了clj的論文。

clj的論文中對性質的研究比較深入

以下是clj論文里推薦的一題，題意:給一個字符串S，令F(x)表示S的全部長度為x的子串中，出現次數的最大值。求F(1)..F(Length(S))?（感謝clj的翻譯>_<）

首先按順序建SAM。一個串的|Right|就是出現次數。

因為父節點的Right集合正好等于子節點Right集合的并集，于是能夠拓撲排序從后往前找，然后每次再把子節點的Right加到pre節點上就可以。這里拓撲排序使用了類似于計數排序的思想。見代碼

#include<iostream>//SAM #include<cstring> #include<cmath> #include<cstdio> #include<algorithm> 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<l;++i) ins(s[i]-'a',i+1);for(int i=1;i<=tot;++i) cnt[step[i]]++;for(int i=1;i<=tot;++i) cnt[i]+=cnt[i-1];for(int i=1;i<=tot;++i) Q[cnt[step[i]]--]=i;for(int i=tot;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; }

總結

以上是生活随笔為你收集整理的SPOJ 8222 NSUBSTR(SAM)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。