【AHOI2013】差异

题面

https://www.luogu.org/problem/P4248

题解

// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#define ri register int
#define N 500050
using namespace std;
char s[N];
long long ans;

struct SAM{
  int ff[N<<1],ch[N<<1][26],len[N<<1],cnt[N<<1],cnts[N<<1];
  vector<int> son[N<<1];
  int las,tot;
  void init() {
    las=tot=1;
  }
  void extend(int c) {
    int np=++tot,p=las; las=np;
    len[np]=len[p]+1; cnt[np]++; cnts[np]++;
    while (p && !ch[p][c]) ch[p][c]=np,p=ff[p];
    if (!p) ff[np]=1;
    else {
      int q=ch[p][c];
      if (len[q]==len[p]+1) ff[np]=q;
      else {
        int nq=++tot;
        for (ri i=0;i<26;i++) ch[nq][i]=ch[q][i]; ff[nq]=ff[q];
        len[nq]=len[p]+1;
        ff[np]=ff[q]=nq;
        while (p && ch[p][c]==q) ch[p][c]=nq,p=ff[p];
      }
    }
  }
  
  void treesum(int x){
    for (ri i=0;i<son[x].size();i++) {
      treesum(son[x][i]);
      cnt[x]+=cnt[son[x][i]];
    }
  }
  
  void dp(int x){
    long long sum1,sum2;
    for (ri i=1;i<=tot;i++) {
      sum1=sum2=0;
      for (ri j=0;j<son[i].size();j++) sum1+=cnt[son[i][j]],sum2+=cnt[son[i][j]]*1LL*cnt[son[i][j]];
      sum1+=cnts[i];
      sum2+=cnts[i]*cnts[i];
      sum1=sum1*sum1;
      ans-=(sum1-sum2)*1LL*len[i];
    }
  }
  
  void work() {
    for (ri i=1;i<=tot;i++) son[ff[i]].push_back(i);
    treesum(1);
    dp(1);
  }
} sam;

int main(){
  scanf("%s",s+1);
  int n=strlen(s+1);
  sam.init();
  for (ri i=n;i>=1;i--) sam.extend(s[i]-'a');
  ans=(n-1)*1ll*n*1ll*(n+1)/2;
  sam.work();
  cout<<ans<<endl;
}