算法 - KMP

2020-08-05 12:12:32

Kmp 算法比较重要。 是一个字符匹配算法， 做到时间复杂度是$O(n + m)$, 它是是对暴力算法的一个优化， 暴力算法的时间复杂度是$O(n * m)$

暴力算法的思路：

  • i, j 两个指针，i指向匹配串, j 指向模式串
  • i, j 两个指针，如果匹配相等，i, j 指针同时往下跳
  • 如果匹配不等， i 从匹配串开始的地方下一个从新开始匹配。 j 跳会到开头。

暴力算法C++ 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
// ss[N], ms[M], ss表示字符串， ms表示模式串
for(int i = 0; i < n; i++) {
    bool flag = true;
    for(int j = 0; j < m; j++) {
        if (ss[i + j] != ms[j]) {
            flag = false;
            break;
        }
    }

    // 匹配成功， 输出所有匹配成功的起始下标
    if (flag) printf("%d ", i);
}

KMP思路：

绿色之前都是匹配成功的， 在黑色点和黄色点匹配失败。假如存在蓝色的矩阵(最长相等前缀和后缀)，表示该部分都相等。1 = 2 = 3 = 4。所以这时候进行
回退，就不用回退到开始的地方。只用回退到相等的地方，然后从相等的地方继续匹配。

接下来从黑色的点和蓝色的点继续匹配，如果匹配成功，继续匹配，如果不成功。进行回退。如果一直不成功就会回退到0，重新匹配。这就是KMP匹配的过程。

求蓝色的矩阵部分(最长匹配前缀和后缀)就是KMP的核心。用数组表示最长匹配前缀和后缀所以叫next数组。里面存放的是长度，这里有个边界处理如果下角标从1开始，下次该比较的地方就是长度 + 1。

前缀和后缀不能包括整个字符串：

例：

1
2
3
4
5
6
7
8
9
aba

前缀： a, ab
后缀： a ba

abcd:

前缀： a, ab, abc
后缀： d, cd, bcd

KMP算法C++实现：

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
ss[N], ms[M], ne[M]

// 求next数组
// 存放的时候ss 和 ms 都是从1开始的
// j表示最长前缀和后缀的长度
for(int i = 2, j = 0; i <= m; i++) {
    // 如果当前值i和最长前缀和后缀的下一个值不等，j 进行回退。最终会回退到0
    while( j && ms[i] != ms[j + 1]) j = ne[j];
    // 如果相等
    if (ms[i] == ms[j + 1]) j++;
    // next数组存入数据
    ne[i] = j;
}


// 匹配过程
for(int i = 1, j = 0; i <= n; i++) {
    while(j && ss[i] != ms[j + 1]) j = ne[j];
    if (ss[i] == ms[j + 1]) j++;
    // 匹配成功
    if (j == m) {
        // 输出匹配成功时候的起始下标
        printf("%d", i - j);
    }
}

题目： KMP字符串

来源: https://www.acwing.com/problem/content/description/833/

给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串P在模式串S中多次作为子串出现。

求出模板串P在模式串S中所有出现的位置的起始下标。

输入格式
第一行输入整数N，表示字符串P的长度。

第二行输入字符串P。

第三行输入整数M，表示字符串S的长度。

第四行输入字符串S。

输出格式
共一行，输出所有出现位置的起始下标（下标从0开始计数），整数之间用空格隔开。

数据范围

$1≤N≤10^5$

$1≤M≤10^6$

输入样例：

1
2
3
4
3
aba
5
ababa

输出样例：

1
0 2

C++ 实现：

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
#include <iostream>

using namespace std;
const int N = 1e6 + 10;
char ss[N], ms[N];
int n, m, ne[N];

int main() {
    cin >> m >> ms + 1 >> n >> ss + 1;

    // 求next数组
    for(int i = 2, j = 0;i <= m; i++) {
        // 当前值和最长前缀和后缀的下一个值进行比较
        while(j && ms[i] != ms[j + 1]) j = ne[j];
        if(ms[i] == ms[j + 1]) j++;
        ne[i] = j;
    }

    // KMP 匹配过程
    for(int i = 1, j = 0; i <= n; i++) {
        // j = 0 表示模式串的长度为0
        while(j && ss[i] != ms[j + 1]) j = ne[j];
        if (ss[i] == ms[j + 1]) j++;
        if (j == m) {
            printf("%d ", i - j);

            // 匹配成功后回退进行下次匹配
            j = ne[j];
        }
    }

    return 0;
}
  1. 1. 题目： KMP字符串