原题链接：Codeforces432D
题目大意：给定一个字符串 $s$，求满足 $s$ 的前缀匹配 $s$ 的后缀的不同匹配长度的数量，并求满足前面匹配要求的前缀子串在原串的出次数。
$\rm KMP$
解法
先预处理 $\rm Next$ 数组，$s$ 串长度为 $n$，然后从 $n$ 开始回退，统计最多回退的次数，再加上 $1$ 就是第一问的答案（因为这里的后缀不是真后缀）。
如何快速得到满足条件的前缀子串在原串中的出现次数呢？如果 $\mathrm{Next}[j]$ 满足，那么 $\mathrm{Next}[\mathrm{Next}[j]]$ 也一定满足，因此这题可以按照拓扑序，即按匹配长度从大到小递推，将匹配长度为 $\mathrm{Next}[j]$ 的数量累加到匹配长度为 $\mathrm{Next}[\mathrm{Next}[j]]$ 的数量上。
AcWing160-匹配统计是一道类似的题目。
代码
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
| #include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010;
int n;
char p[N];
int ne[N], cnt[N];
bool st[N];
int main() {
scanf("%s", p + 1);
n = strlen(p + 1);
for (int i = 2, j = 0; i <= n; i++) {
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j++;
ne[i] = j;
cnt[j]++;
}
for (int i = n; i >= 1; i--) cnt[ne[i]] += cnt[i];
int k = ne[n], ans = 1;
while (k) {
st[k] = true;
k = ne[k];
ans++;
}
printf("%d\n", ans);
for (int i = 1; i < n; i++) {
if (st[i]) printf("%d %d\n", i, cnt[i] + 1);
}
printf("%d %d\n", n, 1);
return 0;
}
|
