一行，一个字符串S

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

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const int N=;

 int fa[N],ch[N][],len[N],cnt,lst;

 int cntE,fir[N],to[N],nxt[N],dp[N];

 char s[N];

 void Init(){lst=cnt=;}

 void Insert(int c){

     int p=lst,np=lst=++cnt;len[np]=len[p]+;

     while(p&&ch[p][c]==)ch[p][c]=np,p=fa[p];

     if(!p)fa[np]=;

     else{

         int q=ch[p][c],nq;

         if(len[p]+==len[q])

             fa[np]=q;

         else{

             len[nq=++cnt]=len[p]+;

             fa[nq]=fa[q];fa[q]=fa[np]=nq;

             memcpy(ch[nq],ch[q],sizeof(ch[q]));

             while(ch[p][c]==q)ch[p][c]=nq,p=fa[p];

         }

     }

 }

 void addedge(int a,int b){

     nxt[++cntE]=fir[a];

     to[fir[a]=cntE]=b;

 }

 int end[N];

 long long ans;

 void DFS(int x){

     int sum=;

     for(int i=fir[x];i;i=nxt[i]){

         DFS(to[i]);

         ans-=2ll*len[x]*dp[to[i]]*dp[x];

         dp[x]+=dp[to[i]];

     }

 }

 int main(){

     Init();

     scanf("%s",s+);

     int l=strlen(s+);

     ans=1LL*(l-)*(l+)*l/;

     for(int i=l;i>=;i--)

         Insert(s[i]-'a'),dp[lst]+=;

     for(int i=;i<=cnt;i++)

         addedge(fa[i],i);

     DFS();

     printf("%lld\n",ans);

     return ;

 }