【算法】字符串：KMP算法

引言

kmp算法是字符串算法中最简单的一种算法，可以用于一下问题解决（待补充）：

  • 字符串匹配
  • 字符串循环节

但是，我发现有很多人都像我以前一样，其实并不是很懂这个算法。于是，就采用背代码的方式试图理解，但总是徒劳。而我个人认为，唯一可以通过背代码加深理解的只有复杂的数据结构。而这种巧妙的算法不是能通过背来理解的。

关于KMP算法

关于kmp算法的讲解网上有很多，找那种图多的博客看看，基本上讲的都差不多，也都非常明了。

所以，这里我只想讲讲我自己的体会。不画图，纯想：

  • kmp算法的核心是一个next数组（我的代码中为p数组），当我们处于字符串（设为a）的第i个字符处时，求出的next[i]满足数组的前next[i]个字符和以a[i-next[i]+1]～a[i]这next[i]个字符是完全一样的，且next[i]最大，但又不能等于i

上面说的还是有点抽象，那么我们从字符串匹配的角度思考：

  • 现在我们要从a串中找到一个子串和b串完全匹配，假设已经匹配了前i个，但是第（i+1）个不匹配，那么我么就要将字符串b向后移动再次寻求匹配。
  • 既然我们向后移动了b串，那么，如果a中与b串匹配的串的首个字符的位置在i之前，那么这个匹配的子串一定跨越了i这个位置。
  • 那么，我们自然而然就像知道，以a中以i位置结尾的子串最多能与b中的前几个匹配呢？
  • 要回答这个问题，就是取求next数组了。

个人认为，这就是kmp的核心思想了～

而关于next数组的求法，是通过len维护的，看代码很容易理解。这里，强烈推荐我写的kmp算法，个人认为比网上的代码简洁、明了不少。

以下是求next数组（p数组）的代码，关于匹配的代码我后面会给出。

1
2
3
4
5
6
7
8
void get_p() {
    p[0] = 0;
    for (int i = 1, len = 0; i < n; i++) {
        while (len && a[i] != a[len]) len = p[len - 1];
        if (a[i] == a[len]) len++;
        p[i] = len;
    }
}

应用

字符串匹配

前面将原理的时候就是用这个举得例子，直接看代码，和求next数组几乎一样～

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

using namespace std;

char a[20], b[20];
int p[20];
int n, m;

void get_p() {
    p[0] = 0;
    for (int i = 1, len = 0; i < m; i++) {
        while (len && b[i] != b[len]) len = p[len - 1];
        if (b[i] == b[len]) len++;
        p[i] = len;
    }
}

void match() {
    for (int i = 0, len = 0; i < n; i++) {
        while (len && a[i] != b[len]) len = p[len - 1];
        if (a[i] == b[len]) len++;
        if (len == m) {
            cout << "match at " << i - len + 1 << endl;
            len = p[len];
        }
    }
}

int main() {
    cin >> a >> b;
    n = strlen(a);
    m = strlen(b);
    get_p();
    match();
    return 0;
}

循环节

设字符串长度为n。既然字符串的前p[n-1]个字符和后p[n-1]个字符完全相同，且p[n-1]最大了，那么最大循环节的长度就是（n-p[n-1]）了～