模板

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

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