后缀自动机模板

#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <ctime> #include <vector> #include <queue> #include <stack> #include <deque> #include <string> #include <map> #include <set> #include <list> #define M(a,b) memset(a,b,sizeof(a)) typedef long long LL; using namespace std; const int MAXL=1000005; const int MAXS=26; struct SAM { int n=0, len, st; //maxlen表示每个状态对应的子串中长度最大值，minlen最小值 //trans是转移边，根节点是1，所以0代表不存在 //slink表示绿色的suffix link //col表示节点颜色，col=1代表是后缀节点，=0代表不是后缀的节点 //indeg表示对于只含有suffix link的图的度，统计endposamu用 //endposa表示该状态对应的子串们出现的结尾位置，amu表示endpos集合的大小 //ans表示某一长度的子串的个数 //sam中每个状态字符串长度是连续的，要求某个状态对应的子串个数只需maxlen-minlen+1即可 int maxlen[2*MAXL+10], minlen[2*MAXL+10], trans[2*MAXL+10][MAXS], slink[2*MAXL+10], col[2*MAXL+10], indeg[2*MAXL+10], endposamu[2*MAXL+10], ans[MAXL]; int new_state(int _maxlen, int _minlen, int* _trans, int _slink) { n++; maxlen[n]=_maxlen; minlen[n]=_minlen; for(int i=0; i<MAXS; i++) { if(_trans==NULL) trans[n][i]=0; else trans[n][i]=_trans[i]; } slink[n]=_slink; return n; } int add_char(char ch, int u) { int c=ch-'a'; int z=new_state(maxlen[u]+1, -1, NULL, 0); col[z]=1; int v=u; while(v!=0&&trans[v][c]==0) { trans[v][c]=z; v=slink[v]; } if(v==0)//最简单的情况，suffix-path(u->S)上都没有对应字符ch的转移 { minlen[z]=1; slink[z]=1; indeg[1]++; return z; } int x=trans[v][c]; if(maxlen[v]+1==maxlen[x])//较简单的情况，不用拆分x { minlen[z]=maxlen[x]+1; slink[z]=x; indeg[x]++; return z; } int y=new_state(maxlen[v]+1, -1, trans[x], slink[x]); //最复杂的情况，拆分x col[y]=0; minlen[x]=maxlen[y]+1; slink[x]=y; minlen[z]=maxlen[y]+1; slink[z]=y; indeg[y]+=2; int w=v; while(w!=0&&trans[w][c]==x) { trans[w][c]=y; w=slink[w]; } minlen[y]=maxlen[slink[y]]+1; return z; } void init() { memset(col, 0, sizeof(col)); memset(indeg, 0, sizeof(indeg)); memset(maxlen, 0, sizeof(maxlen)); memset(minlen, 0, sizeof(maxlen)); memset(trans, 0, sizeof(maxlen)); memset(slink, 0, sizeof(maxlen)); memset(endposamu, 0, sizeof(endposamu)); n=0;//多case也要清空n st=new_state(0, -1, NULL, 0); } void getendpos() { queue<int> que; for(int i=st;i<=n;i++) { if(indeg[i]==0) que.push(i); if(col[i]==1) endposamu[i]++; } while(!que.empty()) { int pos=que.front();que.pop(); endposamu[slink[pos]]+=endposamu[pos]; indeg[slink[pos]]--; if(indeg[slink[pos]]==0) que.push(slink[pos]); } } void addstring(string s) { int la=st; for(auto tmp:s) { la=add_char(tmp, la); } getendpos(); for(int i=st;i<=n;i++) { ans[maxlen[i]]=max(ans[maxlen[i]], endposamu[i]); } for(int i=s.length()-1;i>=1;i--) { ans[i]=max(ans[i], ans[i+1]); } } }sam; int main() { string s;cin>>s; sam.init(); sam.addstring(s); for(int i=1;i<=s.length();i++) { printf("%d\n", sam.ans[i]); } system("pause"); return 0; }