P4248-[AHOI2013]差异
题目:
题目描述:
给定一个长度为 $n$ 的字符串 $S$，令 $T_i$ 表示它从第 $i$ 个字符开始的后缀。求
$\displaystyle \sum_{1\leqslant i<j\leqslant n}\text{len}(T_i)+\text{len}(T_j)-2\times\text{lcp}(T_i,T_j)$
其中，$\text{len}(a)$ 表示字符串 $a$ 的长度，$\text{lcp}(a,b)$ 表示字符串 $a$ 和字符串 $b$ 的最长公共前缀。
输入格式:
一行，一个字符串 $S$。
输出格式:
一行，一个整数，表示所求值。
样例:
样例输入1:
样例输出1:
思路:
实现:
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
| // Problem: P4248 [AHOI2013]差异
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4248
// Memory Limit: 500 MB
// Time Limit: 2000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)
#include "ybwhead/SAM.h"
#include "ybwhead/ios.h"
CPTH::SAM<> x;
long long ans = 0;
const int maxn = 1e6 + 10;
int cnt[maxn];
int main()
{
string s;
yin >> s;
int n = s.size();
reverse(s.begin(), s.end());
for (auto c : s)
cnt[x.append(c)] = 1;
// x = CPTH::SAM<>(s);
x.buildTree();
function<void(int)> dfs1 = [&](int u) {
for (auto v : x.children(u))
{
dfs1(v);
cnt[u] += cnt[v];
ans += (ll)(x[v].len - x[u].len) * cnt[v] * (n - cnt[v]);
// yout << x[v].len << " " << x[u].len << endl;
}
};
dfs1(0);
yout << ans << endl;
return 0;
}
|