【KMP】Codeforces Round 246 (Div. 2) D. Prefixes and Suffixes （统计每个前缀出现次数）
2021-09-22 16:59:00
# ACM
题链
题目分析
题意给定一个字符串 $s$，对于 $s$ 的任何与后缀匹配的前缀，输出该前缀在字符串中出现次数；
如果统计完每个前缀出现次数，那么与后缀匹配的前缀可以通过跳最后一个字符对应的 $next$ 数组的值来得到；
统计每个前缀出现次数则是 $OI-wiki$ 上的模板算法；
$OI-wiki/string/kmp$
代码实现
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
52
53
54
55
56
| #include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define B1 131
#define B2 13331
#define M1 1000000007
#define M2 1000000009
#define eps 1e-8
#define MAXN 9e18
#define MS 1000009
int n,m,k;
char s[MS];
int skmp[MS];
int cnt[MS];
struct node{
int len, val;
}ac[MS];
int tot;
void get_skmp(){
for(int i=2,j=0;i<=n;i++){
while(j && s[i] != s[j+1]) j = skmp[j];
if(s[i] == s[j+1]) j++;
skmp[i] = j;
}
}
void solve(){
cin >> s+1;
n = strlen(s+1);
get_skmp();
for(int i=0;i<=n;i++) cnt[i] = 1;
for(int i=n;i>=1;i--) cnt[skmp[i]] += cnt[i];
for(int j=n;j;j=skmp[j]){
ac[++tot] = {j,cnt[j]};
}
cout << tot << "\n";
for(int i=tot;i>=1;i--){
cout << ac[i].len << " " << ac[i].val << "\n";
}
}
int main(){
ios::sync_with_stdio(false);
int ce = 1;
while(ce--){
solve();
}
}
|
2021-09-22 16:59:00
# ACM
