一行，一个字符串S

一行，一个整数，表示所求值

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 const int N=1000010; 6 int fa[N],ch[N][26],len[N],cnt,lst; 7 int cntE,fir[N],to[N],nxt[N],dp[N]; 8 char s[N]; 9 void Init(){lst=cnt=1;}10 void Insert(int c){11     int p=lst,np=lst=++cnt;len[np]=len[p]+1;12     while(p&&ch[p][c]==0)ch[p][c]=np,p=fa[p];13     if(!p)fa[np]=1;14     else{15         int q=ch[p][c],nq;16         if(len[p]+1==len[q])17             fa[np]=q;18         else{19             len[nq=++cnt]=len[p]+1;20             fa[nq]=fa[q];fa[q]=fa[np]=nq;21             memcpy(ch[nq],ch[q],sizeof(ch[q]));22             while(ch[p][c]==q)ch[p][c]=nq,p=fa[p];23         }    24     }25 }26 27 void addedge(int a,int b){28     nxt[++cntE]=fir[a];29     to[fir[a]=cntE]=b;30 }31 int end[N];32 long long ans; 33 void DFS(int x){34     int sum=0;35     for(int i=fir[x];i;i=nxt[i]){36         DFS(to[i]);37         ans-=2ll*len[x]*dp[to[i]]*dp[x];38         dp[x]+=dp[to[i]];39     }        40 }41 42 int main(){43     Init();44     scanf("%s",s+1);45     int l=strlen(s+1);46     ans=1LL*(l-1)*(l+1)*l/2;47     for(int i=l;i>=1;i--)48         Insert(s[i]-‘a‘),dp[lst]+=1;49     50     for(int i=2;i<=cnt;i++)51         addedge(fa[i],i);52     DFS(1);    53     printf("%lld\n",ans);54     return 0;55 }