KMP

2020-07-21

这段时间噬月在进行数据结构和算法的复习和学习！

这篇博客将包括广为人知的KMP算法以及关于其思路的讨论。

本篇算法模板来自AcWing的y总。

本篇博客提到的字符串都从下标1开始储存。

KMP字符串匹配算法

考虑这样一个问题：给定一个长长的字符串，我们称为模式串，再给定一个（相对而言）短短的字符串，我们称为模板串。已知模板串在模式串中出现一次或多次，我们需要求出，模板串究竟出现过几次，以及每一次出现的起始坐标在哪里。

刚看到这个问题的时候，噬月蒟蒻是大呼简单的，他（也就是我）抬手就写下了如下代码：

// 假如模式串s长为n，模板串p长为m
for (int i = 0; i < n; ++ i ) {
    bool flag = true;
    for (int j = 0; j < m; ++ j ) {
        if (i + j >= n || s[i + j] != p[j]) {
            flag = false;
            break;
        }
    }
    if (flag) {
        cout << i << endl;
    }
}

噬月蒟蒻一度认为这个直观且暴力的解法属于优良题解，直到遇到了KMP算法，当然这是题外话。

在此我们不妨看一下这个解法，思考一下它为什么被称为暴力的。惹眼的当然是不由分说的两重for循环嵌套，外层循环遍历了模式串，显然是枚举了其各个子串的起点；内层则遍历了模板串，与模式串的各个子串进行了比较。这种算法兢兢业业地枚举了每一个可能的起点，并尽可能匹配了每一个起点所能匹配到的最长匹配串——尽管这当中可能做了无用功。无用功在哪里？让我们来看一个例子：

模式串 s : 111011000000001
模板串 p : 1110111

现在从头开始匹配：
111011000000001
1110111
显然，匹配到模板串的第四个字符时就会停下并跳出
——然后我们的暴力算法接下来会做什么呢？它会以这种姿势继续匹配：
111011000000001
 1110111
外层循环下标加1，然后继续匹配字符串。

就在这时，我们可以停下来仔细端详这个算法做的事情：在第一次匹配的过程中，它遍历过了两个字符串的前六个字符，发现全部匹配，而在发现第七个字符不匹配时，让内层循环终止，并让指向模式串的指针（不是真的指针，而是指外层循环的i）加一，而指向模板串的指针（不是真的指针，而是指内层循环的j）则从0开始重新匹配。看到这里也许你要说：这些道理我都懂，所以无用功在哪里？

在这样问的时候，我们其实是没有意识到，局部的成功匹配实际上传达了更多的信息。匹配的过程是模板串在模式串中“发现自己”的过程，局部的成功匹配则意味着它“发现了局部的自己”。这实际上反映了，匹配的过程和模板串自身有很强的联系——这同时意味着，只要我们对模板串更加了解，就可以加速匹配的过程。这种定性的讲法十分玄乎而且没有说服力，我们不妨依然来看上面的例子，不过这次是更加一般的情况。

假设在一个长长的字符串的匹配过程中我们发现了六个匹配的字符，并且在发现第七个字符不匹配之后令i加了1，接下来的情形在任何一个字符串中间，看起来像这样：

1 2	...111011... 1110111

但我们可以发现，中间的0和1显然不可能匹配，让程序一步跳一格，去执行这种明知不匹配的情况，岂不是在做无用功？那它应该跳到哪里呢？我们希望它跳到一个位置，这个位置既不是傻乎乎的每次都前进一格：

1 2	...111011... 1110111

也不是跳过了头导致漏掉了一些字符没有匹配到：

1 2	...111011... 1110111

我们希望它最好一步到位，跳成这样：

1 2	...111011... 1110111

你可能想说：拉倒吧，我们用眼睛看，当然知道是无用功，程序怎么会知道它的第三个字符不匹配？又怎么会知道它需要一步跳到这里继续匹配？~~你是写程序还是搞玄学？~~ 其实我想说，为了解释这种方法的可行性，我已经做了足够的铺垫描述：我们刚刚讨论过，任何局部匹配的字符串都是模板串的子串，而我们希望执行的这个最理想的跳转正是由这个已经匹配到的子串决定的——是否会做无用功，是否有漏掉可能的匹配，这个子串都可以作为标准来确定我们究竟要往前跳多少。而好消息是，我们早就知道了模板串是什么样子的——因此我们知道它的所有子串是什么样子的，这就给了我们机会来进行预处理，从而检索出模板串所有下标对应的理想跳转，从而在匹配字符串的时候达到最高效率。

如果你能够透过我凌乱的描述，理解了这个方法的可行之处，那么恭喜你，你已经理解了KMP对暴力字符串匹配算法的核心优化点。

现在问题来了：我们要如何找到这样的理想跳转？对于任何字符串s，当s与自己错开n格时，假设有前k个字符依然匹配，这意味着该字符串s中，$[1, k]$区间中的字符和$[n + 1, n + k]$区间中的字符完全相等。而又不难发现，$strlen(s) = n + k$，因此我们也可以这样说：这种情况下，字符串s中有一个长度为k的前缀和它的长度为k的后缀完全相等。

可以画图辅助理解

因此我们需要求得一个数组next，next[i] = j表示在模式串s中，有一个以模式串开头下标为起始下标，以下标i为结尾下标的子串，这个子串中有一个长度为j的前缀和它的长度为j的后缀完全相等。

而当我们的场景是匹配字符串时，我们希望错开的n尽量小，这样就不会漏掉任何可能匹配的字符串，因此这个前缀/后缀是最长的。

到此为止，如果我们正确理解了这个数组的含义，并在读入字符串的时候令字符串下标从1开始，就不难理解KMP算法匹配模式串的过程：

// 由于next可能被cpp库函数定义过，我们写作ne
// p[N]为模板串，s[M]为模式串
for (int i = 1, j = 0; i <= m; ++ i ) {
    while (j && s[i] != p[j + 1]) {
        // 只要j还没有跳转到0，并且下一个字符并不匹配，就继续跳转
        j = ne[j];
    }
    if (s[i] == p[j + 1]) {
        // 字符匹配，则继续向前
        ++ j ;
    }
    if (j == n) {
        // 所有字符都匹配，则匹配成功
    }
}
// 注：j从0开始，j + 1指向模板串下一个要匹配的字符

实际上，要理解KMP匹配模式串的过程，关键在于理解next数组的意义，而假如你理解了，想必你接下来的主要问题就会和我一样：这么神奇的数组它是怎么求出来的？

既然是求最长的子串前后缀，想必也是匹配字符串的工作，我们可以先看一下求这个数组的代码：

for (int i = 2, j = 0; i <= n; ++ i) {
    while (j && p[i] != p[j + 1]) {
        j = ne[j];
    }
    if (p[i] == p[j + 1]) {
        ++ j ;
    }
    ne[i] = j;
}

然后我就震惊地发现：这和KMP匹配模式串也太像了吧！然后我接着就乱了：这难道是在求next数组的时候也用了KMP？这不就递归了吗……

希望你没有像我一样把自己搞晕——我们这就来理清求next数组的思路。

由于我们的字符串都是从1开始储存的，那么我们就从下标1开始讨论。首先，next[1] = 0是显然的，当只有第一个字符匹配的时候，退无可退，我们只能从0开始重新匹配。而在接下来的匹配过程中，我们实际上要做这样一个事情：将模板串的开头和所有可能的子串结尾进行校对。为什么是模板串的开头呢？因为所有可能在匹配过程中出现的局部匹配子串，都只能是从头开始匹配，这是废话显然的。而模板串的所有位置显然都是可能的子串结尾——于是，我们就会手拿两个模板串做这样的事情：把其中一根的开头对到另一根的开头上，依次校对过去，如果一直相等，就一直记录相等的字符数，因为这就是最长的相等的前/后缀；如果遇到了不相等的字符，就把下面的字符串往前挪，尝试校对出更短的相等的前/后缀，看起来就像是：

校对过程

确实很像！匹配过程中的每一次i自增，都会记录一次j，这个j就是当前找到的最大的相等前后缀的长度（如果p[i] == p[j + 1]始终成立，那么显然找到的j就是不断增加的，对于每一个以i结尾的子串来说，显然这样的j就是最大的）。假设在某一段匹配的过程中，字符始终相等（绿色框），那么i和j就会齐头并进，直到遇到不相等的字符（红色框）：

校对过程

这时，i指向了上面的红色框，j则指向下面红色框前面的绿色框，我们实际上就找到了ne[i] = j这是不难理解的。接下来的情况十分面善：我们面临了一个跳转的问题，即j是要从0开始匹配，还是可以从某个更优的下标开始？我们可以观察到，我们已经确定了next[1] = 0，因此在开始匹配的时候，我们就令i = 2，而i只会自增，j则是不一定自增。i始终是领先j的，这意味着，对于匹配过程中的任何时刻，ne[j]都是已知的！因此才有了这个和匹配模式串时一模一样的while循环——这个循环能够出现，意味着我们在匹配的过程中也充分利用了已经求出的next数组，这真是十分优美巧妙。

到此为止，KMP算法的思想和实现的步骤已经（凌乱地）讨论完毕了，我们可以借助代码再一次梳理一下。

下面的代码同是是AcWing上KMP字符串的题解：

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;
int ne[N];
char p[N], s[M];
int main() {
    int n, m;
    cin >> n >> p + 1 >> m >> s + 1;
    // 求next
    for (int i = 2, j = 0; i <= n; ++ i ) {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }
    // 匹配模式串
    for (int i = 1, j = 0; i <= m; ++ i ) {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n) {
            // 成功时输出起始下标
            printf("%d ", i - n);
            j = ne[j];
        }
    }
    return 0;
}