bzoj3238

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 500010
int n,k;
char s[N];
int rank[N],sa[N],temp[N],lcp[N],st[N],l[N],r[N];
inline bool cp(int i,int j)
{
    if(rank[i]!=rank[j]) return rank[i]<rank[j];
    int ri=i+k<=n?rank[i+k]:-1;
    int rj=j+k<=n?rank[j+k]:-1;
    return ri<rj;
}
void Sa()
{
    for(int i=1;i<=n;++i)
    {
        rank[i]=s[i]; sa[i]=i;
    }
    for(k=1;k<=n;k<<=1)
    {
        sort(sa+1,sa+n+1,cp);
        temp[sa[1]]=1;
        for(int i=2;i<=n;++i) temp[sa[i]]=temp[sa[i-1]]+(cp(sa[i-1],sa[i]));
        for(int i=1;i<=n;++i) rank[i]=temp[i];
    }
}
void Lcp()
{
    for(int i=1;i<=n;++i) rank[sa[i]]=i;
    int h=0;
    for(int i=1;i<=n;++i)
    {
        if(rank[i]<=1) continue;
        int j=sa[rank[i]-1];
        if(h>0) --h;
        for(;i+h<=n&&j+h<=n;++h) if(s[i+h]!=s[j+h]) break;
        lcp[rank[i]-1]=h;
        l[rank[i]-1]=r[rank[i]-1]=rank[i]-1;
    }
}
void solve()
{
    n=strlen(s+1);
    Sa(); Lcp();
    int top=0;
    for(int i=1;i<n;++i)
    {
        while(top&&lcp[i]<=lcp[st[top]]) r[st[top-1]]=r[st[top]],l[i]=l[st[top--]];
        st[++top]=i;
    }
    while(top) r[st[top-1]]=r[st[top--]];   
    ll ans=(ll)n*(ll)(n-1)*(ll)(n+1)>>1;
    for(int i=1;i<n;++i) ans-=2*(ll)(r[i]-i+1)*(ll)(i-l[i]+1)*(ll)lcp[i];
    printf("%lld\n",ans);
}
int main()
{
    scanf("%s",s+1);
    solve();
    return 0;
}