Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define gc c=getchar()
- #define r(x) read(x)
- #define ll long long
- template<typename T>
- inline void read(T&x){
- x=0;T k=1;char gc;
- while(!isdigit(c)){if(c=='-')k=-1;gc;}
- while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
- }
- const int N=1e6+7;
- int len[N];
- int to[N][26];
- int fa[N];
- int siz[N];
- int tot;
- inline int NewNode(int l,int *tr,int su){
- ++tot;
- len[tot]=l;
- if(tr!=NULL)memcpy(to[tot],tr,26<<2);
- fa[tot]=su;
- return tot;
- }
- inline int insert(int u,int c){
- int t=NewNode(len[u]+1,NULL,0);
- for(;u&&!to[u][c];u=fa[u])to[u][c]=t;
- if(!u){
- fa[t]=1;
- return t;
- }
- int v=to[u][c];
- if(len[v]==len[u]+1){
- fa[t]=v;
- return t;
- }
- int x=NewNode(len[u]+1,to[v],fa[v]);
- fa[t]=fa[v]=x;
- for(;u&&to[u][c]==v;u=fa[u])to[u][c]=x;
- return t;
- }
- int ord[N];
- int cnt[N];
- char s[N];
- int main(){
- scanf("%s",s);
- int n=strlen(s);
- int lst=NewNode(0,NULL,0);
- for(int i=0;i<n;++i){
- siz[lst=insert(lst,s[i]-'a')]=1;
- }
- ll ans=(ll)n*(n-1)*(n+1)/2;
- for(int i=1;i<=tot;++i)cnt[len[i]]++;
- for(int i=1;i<=n;++i)cnt[i]+=cnt[i-1];
- for(int i=1;i<=tot;++i)ord[cnt[len[i]]--]=i;
- for(int i=tot;i;--i){
- int x=ord[i];
- ans-=(ll)siz[fa[x]]*siz[x]*len[fa[x]]*2;
- siz[fa[x]]+=siz[x];
- }
- printf("%lld\n",ans);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement