BZOJ 3238 差异 [后缀自动机]

题目

一个长度为n的字符串S,令 Ti 表示它从第i个字符开始的后缀.求

∑1≤i<j≤nlen(Ti)+len(Tj)−2∗lcp(Ti,Tj) 其中len(a)表示字符串a的长度,lcp(a,b)表示字符串a和字符串b的最长公共前缀.

输入

一行，一个字符串S

输出

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

样例输入

cacao

样例输出

54

注意

2≤N≤500000 ,S由小写英文字母组成

分析

这道题需要我们记住一个结论 ! ! !

!反串建后缀自动机的parent树是原串的后缀树!

对于这道题,我们不难发现,原串后缀树上两节点的最近公共祖先的层数就是两子串的lcp,我们可以从叶子结点开始往父亲节点走,根据题目要求就是求出所有公共前缀,我们可以边记录边更新,具体操作可以参考代码第63,64行!

完整代码

#include<bits/stdc++.h> #define maxn 500010 #define maxt 1000010 //#define DEBUG using namespace std; int n; long long ans=0; int sum[maxt],tmp[maxt]; long long total[maxt]; char ch[maxn]; struct SAM { int root,last,tot; int r[maxt],fa[maxt],son[maxt][26],maxl[maxt]; int addnode(int x) { return maxl[++tot]=x,tot; } void init() { root=last=tot=1; } void add(int pos) { int x=ch[pos]-'a',p=last,np=addnode(maxl[p]+1); last=np,r[np]=total[np]=1; for( ; p&&!son[p][x] ; p=fa[p] ) son[p][x]=np; if(!p) fa[np]=root; else { int q=son[p][x]; if(maxl[q]==maxl[p]+1) fa[np]=q; else { int nq=addnode(maxl[p]+1); memcpy(son[nq],son[q],sizeof(son[q])); fa[nq]=fa[q]; fa[q]=fa[np]=nq; for( ; son[p][x]==q ; p=fa[p] ) son[p][x]=nq; } } } void Tsort() { for(int i=1;i<=tot;++i) sum[maxl[i]]++; for(int i=1;i<=n;++i) sum[i]+=sum[i-1]; for(int i=1;i<=tot;++i) tmp[sum[maxl[i]]--]=i; } void treeDP() { for(int i=tot;i;--i) r[fa[tmp[i]]]+=r[tmp[i]]; for(int i=tot;i;--i) { int x=tmp[i]; ans+=1ll*total[fa[x]]*r[x]*maxl[fa[x]]; //不加1ll可能会溢出! total[fa[x]]+=r[x]; //63,64为核心步骤! } } void build() { init(); scanf("%s",ch+1); n=strlen(ch+1); for(int i=n;i;--i) add(i); Tsort(); treeDP(); } } sam ; int main() { #ifdef DEBUG freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif sam.build(); printf("%lld\n",1ll*(n-1)*(n+1)*n/2-ans*2); return 0; }