P4248 [AHOI2013]差异

FxorG · 2021-07-07 21:22:03 · 个人记录

\text{Solution}

后缀树

好像没啥好讲的。

\text{Code}

/* 前面那个len(T_i)+len(T_j)我会O(n)

2*lcp(Ti,Tj)建后缀树

考虑内部的节点乱连
和u点连除自己外的子树节点

lcp长度为len[u] 

由于无序点对，所以不用乘2 

*/ 

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>

#define N (int)(1.5e6)
#define int long long

using namespace std;

struct edge {
    int nex,to;
}e[N];

char s[N];
int head[N],cnt,fa[N],son[26][N],len[N],sz[N];
int ans=0,n,las=1,tot=1;

void ins(int c) {
    int pre=las,x=++tot; las=x; len[x]=len[pre]+1; sz[x]=1;
    for(;pre&&!son[c][pre];pre=fa[pre]) son[c][pre]=x;
    int y=son[c][pre];
    if(!y) fa[x]=1;
    else if(len[y]==len[pre]+1) fa[x]=y;
    else {
        int p=++tot; len[p]=len[pre]+1; 
        fa[p]=fa[y]; fa[x]=fa[y]=p;
        for(int i=0;i<26;i++) son[i][p]=son[i][y];
        for(;pre&&son[c][pre]==y;pre=fa[pre]) son[c][pre]=p;
    } 
}

void add_edge(int x,int y) {
    e[++cnt]=edge{head[x],y};
    head[x]=cnt;
}

void dfs(int x) {
    int qwq=sz[x]; //这个edp等价类有的字符串数量
    for(int i=head[x];i;i=e[i].nex) {
        int y=e[i].to;
        dfs(y); sz[x]+=sz[y];
    } 
    for(int i=head[x];i;i=e[i].nex) {
        int y=e[i].to;
        ans-=(sz[x]-sz[y])*sz[y]*len[x];
    }
    ans-=qwq*(sz[x]-qwq)*len[x];
}

signed main() {
    scanf("%s",s+1); n=strlen(s+1);
    for(int i=n;i>=1;i--) ins(s[i]-'a');
    for(int i=2;i<=tot;i++) add_edge(fa[i],i);
    //ll ans=0;
    for(int i=1;i<=n;i++) ans+=(n-i)*i+(i+1+n)*(n-i)/2;
    dfs(1);
    printf("%lld",ans);
    return 0;
}