1 struct SAM{ 2 int ch[maxn][26],fa[maxn],len[maxn],cnt,last; 3 void Init() 4 { 5 memset(ch,0,sizeof(ch)); 6 memset(fa,0,sizeof(fa)); 7 last=cnt=1; 8 } 9 void Add(int c) 10 { 11 int p=last,np=last=++cnt; 12 len[np]=len[p]+1; 13 while(!ch[p][c]&&p){ 14 ch[p][c]=np;p=fa[p]; 15 } 16 if(p==0) 17 fa[np]=1; 18 else{ 19 int q=ch[p][c]; 20 if(len[p]==len[q]-1){ 21 fa[np]=q; 22 } 23 else{ 24 int nq=++cnt;len[nq]=len[p]+1; 25 memcpy(ch[nq],ch[q],sizeof(ch[q])); 26 fa[nq]=fa[q];fa[q]=fa[np]=nq; 27 while(ch[p][c]==q&&p){ 28 ch[p][c]=nq; 29 p=fa[p]; 30 } 31 } 32 } 33 } 34 };
然后是自整理最全SAM模版，超级大杀器！
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 const int N=200010; 6 char s[N]; 7 int fa[N],pos[N],vis[N],sa[N],rank[N]; 8 int son[N][26],end[N],rht[N],lcp[N]; 9 int ch[N][26],len[N],id[N],tot; 10 int od[N],wv[N],lst,cnt; 11 12 void Init(){ 13 memset(ch,0,sizeof(ch)); 14 memset(end,0,sizeof(end)); 15 memset(son,0,sizeof(son)); 16 memset(vis,0,sizeof(vis)); 17 lst=cnt=1;tot=0; 18 } 19 20 void Insert(int c){ 21 int p=lst,np=lst=++cnt;end[lst]=1; 22 id[len[np]=len[p]+1]=np;rht[np]=1; 23 while(p&&!ch[p][c])ch[p][c]=np,p=fa[p]; 24 if(!p)fa[np]=1; 25 else{ 26 int q=ch[p][c],nq; 27 if(len[q]==len[p]+1)fa[np]=q; 28 else{ 29 len[nq=++cnt]=len[p]+1; 30 fa[nq]=fa[q];fa[q]=fa[np]=nq; 31 memcpy(ch[nq],ch[q],sizeof(ch[q])); 32 while(ch[p][c]==q)ch[p][c]=nq,p=fa[p]; 33 } 34 } 35 } 36 37 void Get_Right(){ 38 for(int i=1;i<=cnt;i++)wv[len[i]]++; 39 for(int i=1;i<=cnt;i++)wv[i]+=wv[i-1]; 40 for(int i=1;i<=cnt;i++)od[wv[len[i]]--]=i; 41 for(int i=cnt;i>=1;i--)rht[fa[od[i]]]+=rht[od[i]]; 42 } 43 44 void Build_Tree(){ 45 int l=strlen(s+1); 46 for(int i=l;i>=1;i--)Insert(s[i]-'a'); 47 for(int i=l;i>=1;i--) 48 for(int x=id[i],p=l+1;x&&!pos[x];x=fa[x]) 49 p-=len[x]-len[fa[x]],pos[x]=p; 50 for(int x=2;x<=cnt;x++)son[fa[x]][s[pos[x]]-'a']=x; 51 } 52 53 void DFS(int x,int l){ 54 if(end[x])sa[rank[l-len[x]+1]=++tot]=l-len[x]+1; 55 for(int i=0;i<26;i++)if(son[x][i])DFS(son[x][i],l); 56 } 57 58 void Build_SA(){ 59 int l=strlen(s+1),k=0;DFS(1,l); 60 for(int i=1,j;i<=l;lcp[rank[i++]]=k) 61 for(k?k--:k,j=sa[rank[i]-1];s[i+k]==s[j+k];k++); 62 } 63 64 int main(){ 65 //freopen(); 66 //freopen(); 67 Init(); 68 scanf("%s",s+1); 69 int l=strlen(s+1); 70 Build_Tree();Build_SA(); 71 for(int i=1;i<=l;i++)printf("%d ",sa[i]);printf(" "); 72 for(int i=2;i<=l;i++)printf("%d ",lcp[i]);printf(" "); 73 return 0; 74 }
警告：这里的SAM都是naive-sam，无法跑trie和多串。