BZOJ3238 [Ahoi2013]差异

佚名 6年前 (2019-05-08) 随笔 2035人围观抢沙发百度已收录

差异

题目描述

给定一个长度为 $n$ 的字符串 $S$，令 $T_i$ 表示它从第 $i$ 个字符开始的后缀。求

$\displaystyle \sum_{1\leqslant i<j\leqslant n}\text{len}(T_i)+\text{len}(T_j)-2\times\text{lcp}(T_i,T_j)$

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

其中，$\text{len}(a)$ 表示字符串 $a$ 的长度，$\text{lcp}(a,b)$ 表示字符串 $a$ 和字符串 $b$ 的最长公共前缀。

输入输出格式

输入格式：

一行，一个字符串 $S$。

输出格式：

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

输入输出样例

输入样例#1： 复制

cacao

输出样例#1： 复制

说明

对于 100% 的数据，保证 $2\leqslant n\leqslant 500000$，且均为小写字母。

分析

参照张天扬《后缀自动及及其应用》。

把串反向，然后求的是前缀串两两的最长公共后缀。定位前缀串在后缀自动机上的位置以后，这个最长公共后缀就是他们在parent树上的lca。

那么简单计数统计即可。时间复杂度$O(n)$

代码

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0;rg char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-') data=-data;
    for(;isdigit(ch);ch=getchar()) data=data*10+ch-'0';
    return data;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;

co int N=1e6;
int last=1,tot=1;
int ch[N][26],fa[N],len[N],s[N],w[N];
void extend(int c){
    int p=last,cur=last=++tot;
    len[cur]=len[p]+1,s[cur]=w[cur]=1;
    for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=cur;
    if(!p) fa[cur]=1;
    else{
        int q=ch[p][c];
        if(len[q]==len[p]+1) fa[cur]=q;
        else{
            int clone=++tot;
            memcpy(ch[clone],ch[q],sizeof ch[q]);
            fa[clone]=fa[q],len[clone]=len[p]+1;
            fa[cur]=fa[q]=clone;
            for(;ch[p][c]==q;p=fa[p]) ch[p][c]=clone;
        }
    }
}
char str[N];
int n,cnt[N],id[N];
int main(){
    scanf("%s",str+1),n=strlen(str+1);
    for(int i=n;i>=1;--i) extend(str[i]-'a');
    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) id[cnt[len[i]]--]=i;
    for(int i=tot;i;--i) s[fa[id[i]]]+=s[id[i]];
    ll ans=0;
    for(int i=1;i<=tot;++i){
        ans+=(ll)w[fa[i]]*s[i]*len[fa[i]];
        w[fa[i]]+=s[i];
    }
    printf("%lld\n",(ll)(n-1)*(n+1)*n/2-2*ans);
    return 0;
}