题意：求所有后缀两两之间的最长公共前缀的长度之和。
解：这道题让我发现了一个奇妙的性质：所有后缀两两最长公共前缀长度之和 和 所有前缀两两最长公共后缀之和的值是相等的，但是每一组公共前/后缀是不同的。
因为这道题要反建后缀自动机，我正建然后过了......
两个串的最长公共后缀就是在fail树上的lca。
所以反建后缀自动机，所有后缀就是主链。然后求这些两两的lca计算每个点作为lca被统计了多少次，树上DFS一遍就好了。
#include <cstdio>
#include <algorithm>
#include <cstring> typedef long long LL;
const int N = ; struct Edge {
int nex, v;
}edge[N]; int top; int tr[N][], len[N], fail[N], cnt[N], tot = , last = ;
int e[N], siz[N];
LL ans;
char s[N]; inline void add(int x, int y) {
top++;
edge[top].v = y;
edge[top].nex = e[x];
e[x] = top;
return;
} inline void insert(char c) {
int f = c - 'a';
int p = last, np = ++tot;
last = np;
len[np] = len[p] + ;
cnt[np] = ;
while(p && !tr[p][f]) {
tr[p][f] = np;
p = fail[p];
}
if(!p) {
fail[np] = ;
}
else {
int Q = tr[p][f];
if(len[Q] == len[p] + ) {
fail[np] = Q;
}
else {
int nQ = ++tot;
len[nQ] = len[p] + ;
fail[nQ] = fail[Q];
fail[Q] = fail[np] = nQ;
memcpy(tr[nQ], tr[Q], sizeof(tr[Q]));
while(tr[p][f] == Q) {
tr[p][f] = nQ;
p = fail[p];
}
}
}
return;
} inline void prework() {
for(int i = ; i <= tot; i++) {
add(fail[i], i);
//printf("add : %d %d \n", fail[i], i);
}
return;
} void DFS(int x) {
siz[x] = cnt[x];
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
DFS(y);
if(x > ) {
ans += 1ll * siz[x] * siz[y] * len[x];
}
siz[x] += siz[y];
}
//printf("x = %d siz = %d \n", x, siz[x]);
return;
} int main() {
LL sum = ;
scanf("%s", s);
int n = strlen(s);
for(int i = ; i < n; i++) {
insert(s[i]);
sum += 1ll * (n - ) * (i + );
}
prework();
DFS();
printf("%lld\n", sum - * ans);
//printf("%lld - %lld \n", sum, 2 * ans);
return ;
}
AC代码(伪)