luogu P4248 [AHOI2013]差异
链接
思路
(sumlimits_{1<=i<j<=n}{{len}(T_i)+{len}(T_j)-2*{lcp}(T_i,T_j)})
=(sumlimits_{1<=i<j<=n}{{len}(T_i)+{len}(T_j)}-sumlimits_{1<=i<j<=n}2*{lcp}(T_i,T_j))
前半部分是(frac{n*(n+1)(n-1)}{2})
后半部分用sam求出parent tree的siz的过程中求解就行了。
两个串的lcp就是他们的lca的longest。
考虑子树内的贡献就行了。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7;
int n,c[N<<1],a[N<<1];
char s[N];
struct sam {
int len,fa,ch[26];
}dian[N<<1];
int siz[N<<1],las=1,tot=1;
void add(int c,int k_th) {
int p=las;int np=las=++tot;
dian[np].len=dian[p].len+1;
for(;p&&!dian[p].ch[c];p=dian[p].fa) dian[p].ch[c]=np;
if(!p) dian[np].fa=1;
else {
int q=dian[p].ch[c];
if(dian[q].len==dian[p].len+1) dian[np].fa=q;
else {
int nq=++tot;
dian[nq]=dian[q];
dian[nq].len=dian[p].len+1;
dian[q].fa=dian[np].fa=nq;
for(;p&&dian[p].ch[c]==q;p=dian[p].fa)
dian[p].ch[c]=nq;
}
}
siz[las]=1;
}
signed main() {
scanf("%s",s+1);
n=strlen(s+1);
for(int i=n;i>=1;--i) add(s[i]-'a',i);
for(int i=1;i<=tot;++i) c[dian[i].len]++;
for(int i=1;i<=tot;++i) c[i]+=c[i-1];
for(int i=1;i<=tot;++i) a[c[dian[i].len]--]=i;
int ans=1LL*n*(n+1)*(n-1)/2;
for(int i=tot;i>=1;--i) {
ans-=2LL*siz[a[i]]*siz[dian[a[i]].fa]*dian[dian[a[i]].fa].len;
siz[dian[a[i]].fa]+=siz[a[i]];
}
printf("%lld",ans);
return 0;
}