P4248 [AHOI2013]差异
给出一个长度为\(n\)的字符串\(S\)，令\(T_i\)表示它从第\(i\)个字符开始的后缀，求：
\(\sum_{1\leq i<j\leq n}len(T_i)+len(T_j)-2\times lcp(T_i,T_j)\)
做法：
对反串建后缀树。
后缀树的边权记为\(len[i]-len[link[i]]\)。
求后缀树上所有路径长度和，就是答案。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int nxt[maxn][26],link[maxn],len[maxn],sz[maxn],tot=1,lst=1;
string s;
void sam_extend (char c) {
int cur=++tot,p=lst;
sz[cur]=1;
len[cur]=len[lst]+1;
sz[cur]=1;
while (p&&!nxt[p][c-'a']) {
nxt[p][c-'a']=cur;
p=link[p];
}
if (!p) link[cur]=1;
else {
int q=nxt[p][c-'a'];
if (len[p]+1==len[q]) link[cur]=q;
else {
int clone=++tot;
len[clone]=len[p]+1;
for (int i=0;i<26;i++) nxt[clone][i]=nxt[q][i];
link[clone]=link[q];
while (p&&nxt[p][c-'a']==q) {
nxt[p][c-'a']=clone;
p=link[p];
}
link[q]=link[cur]=clone;
}
}
lst=cur;
}
vector<int> g[maxn];
void dfs (int u) {
for (int v:g[u]) {
dfs(v);
sz[u]+=sz[v];
}
}
int main () {
ios::sync_with_stdio(false);
cin>>s;
int n=s.size();
for (int i=s.size()-1;i>=0;i--) {
sam_extend(s[i]);
}
for (int i=2;i<=tot;i++) g[link[i]].push_back(i);
dfs(1);
long long ans=0;
for (int i=2;i<=tot;i++) {
ans+=1ll*sz[i]*(n-sz[i])*(len[i]-len[link[i]]);
}
printf("%lld\n",ans);
}