模板

先贴一段代码:当做模板即可

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
#include <bits/stdc++.h>
#define esp 1e-6
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 5;
const int M = 1e9 + 5;

int nxt[N];
int m, n;
string s, t;
void get_next(){
nxt[0] = -1; //默认下标都是从0开始的
int i = 1, j = 0; // 因为nxt[0] 已经初始化成 -1 了 , 所以i从1开始
while(i < m){
if (j == -1 || t[i] == t[j]){
i++, j++;
if (t[i] != t[j])
nxt[i] = j;
else
nxt[i] = nxt[j];
}
else
j = nxt[j];
}
}

int kmp(){
int i = 0, j = 0;
n = s.length();
m = t.length();
while(i < n && j < m){
if (j == -1 || s[i] == t[j])
i++, j++;
else
j = nxt[j];
}
if (j >= m)
return i - m + 1; // 根据自己的输入输出灵活变通
return -1;
}

int main(){
int T;
scanf("%d", &T);
while(T--){
cin >> s >> t;
get_next();
printf("%d\n", kmp());
}
return 0;
}

可以看一下这个例题
题目链接

应用

  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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//#include <bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define esp 1e-6
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 5;
const int M = 1e9 + 5;

int nxt[N];
char s[N], t[N];
void get_next(){
int i = 1, j = 0;
nxt[0] = -1;
while(i < strlen(s)){
if (j == -1 || s[i] == s[j]){
i ++, j++;
if (s[i] != s[j])
nxt[i] = j;
else
nxt[i] = nxt[j];
}
else
j = nxt[j];
}
}
int cnt = 0;
void kmp(){
int n = strlen(t);
int m = strlen(s);
int i = 0, j = 0;
while(i < n && j < m){
if (j == -1 || t[i] == s[j]){
i++, j++;
}
else {
j = nxt[j];
}
if (j == m){
cnt++;
j = nxt[j]; // 这里很奇妙, 可以自己想一想
}
}
}

int main(){
int T;
scanf("%d", &T);
while(T--){
cnt = 0;
scanf("%s%s", s, t);
get_next();
kmp();
printf("%d\n", cnt);
}
return 0;
}

同样附上一个例题:
题目链接

暂且先写这些, 其他以后再补
其实我复习kmp的目的是为了更好的理解AC自动机, 嘿嘿

1
恰似你一低头的温柔,娇弱水莲花不胜寒风的娇羞, 我的心为你悸动不休。  --mingfuyan