题：http://hihocoder.com/problemset/problem/1445
分析：后缀自动机模板
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; typedef long long ll; const int maxn=1000006; int trans[maxn<<1][26],slink[maxn<<1],maxlen[maxn<<1]; int endpos[maxn<<1]; int last,now,root,len; ///st为起始点 ///n状态总数 ///maxlen表示每个状态对应的子串中长度最大值，minlen最小值 ///trans是转移边，根节点是1，所以0代表不存在 ///slink表示绿色的suffix link ///col表示节点颜色，col=1代表是后缀节点，=0代表不是后缀的节点 ///indeg表示对于只含有suffix link的图的度，统计endposamu用 ///endposa表示该状态对应的子串们出现的结尾位置，amu表示endpos集合的大小 ///ans表示某一长度的子串的个数 ///sam中每个状态字符串长度是连续的，要求某个状态对应的子串个数只需maxlen-minlen+1即可 void init(){ now=last=root=1; memset(trans,0,sizeof(trans)); memset(maxlen,0,sizeof(maxlen)); memset(slink,0,sizeof(slink)); } void extend(int c){ maxlen[++now]=maxlen[last]+1; int p=last,np=now; while(p&&!trans[p][c]){ trans[p][c]=np; p=slink[p]; } if(!p) slink[np]=root; else{ int q=trans[p][c]; if(maxlen[p]+1!=maxlen[q]){ maxlen[++now]=maxlen[p]+1; int nq=now; memcpy(trans[nq],trans[q],sizeof(trans[q])); slink[nq]=slink[q]; slink[q]=slink[np]=nq; while(p&&trans[p][c]==q){ trans[p][c]=nq; p=slink[p]; } } else slink[np]=q; } last=np; endpos[np]=1; } ll all(){ ll ans=0; for(int i=root+1;i<=now;i++){ ans+=maxlen[i]-maxlen[slink[i]];///minlen=maxlen[slink[i]] } return ans; } int main(){ string s; init(); cin>>s; len=s.size(); for(int i=0;i<len;i++) extend(s[i]-'a'); cout<<all()<<endl; return 0; }