假设把原串放在后缀树上，LCP 即后缀树上的 LCA。
看看题目里这个式子，不觉得……很像树上路径长度？
所以可以对于每条边，算它的贡献。
DP 即可。
考虑一条边的贡献。
其实就是 \(len_p - len_{fa_p}\)，又是熟悉的式子。
然后要知道一个性质，后缀树相当于把原串翻转之后插进后缀自动机后的 Parent Tree。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
using namespace std;
const int N = 5e5;
int n,a[(N << 1) + 5],cnt[N + 5];
char s[N + 5];
struct node
{
int ch[26];
int fa,len;
} sam[(N << 1) + 5];
long long ans;
int sz[(N <<1) + 5];
int whole = 1,tot = 1;
void push(int x)
{
int cur = whole,p = whole = ++tot;
sam[p].len = sam[cur].len + 1,sz[p] = 1;
for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
sam[cur].ch[x] = p;
if(!cur)
sam[p].fa = 1;
else
{
int q = sam[cur].ch[x];
if(sam[cur].len + 1 == sam[q].len)
sam[p].fa = q;
else
{
int nxt = ++tot;
sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
sam[cur].ch[x] = nxt;
}
}
}
int main()
{
scanf("%s",s + 1),n = strlen(s + 1);
for(register int i = n;i;--i)
push(s[i] - 'a');
for(register int i = 1;i <= tot;++i)
++cnt[sam[i].len];
for(register int i = 1;i <= n;++i)
cnt[i] += cnt[i - 1];
for(register int i = tot;i;--i)
a[cnt[sam[i].len]--] = i;
for(register int i = tot;i;--i)
ans += (long long)(sam[a[i]].len - sam[sam[a[i]].fa].len) * sz[a[i]] * (n - sz[a[i]]),sz[sam[a[i]].fa] += sz[a[i]];
printf("%lld\n",ans);
}