Knuth Morris Pratt

以下图片为 png 格式，点击放大后为 svg 格式。但 svg 显示需要 Source Code Pro 字体。

概述

Knuth-Morris-Pratt 是一种高效的字符串查找算法，用于在一段文本中查找特定子串。

示例

假设我们要在字符串BBC ABCDAB ABCDABCDABDE中查找ABCDABD。
为了方便，下文简称BBC ABCDAB ABCDABCDABDE为S，ABCDABD为K；N为S的长度，M为K的长度。

首先，我们要比较S[0]和K[0]，因为S[0] != K[0]，所以K往后移一位。

又因为此时S[1] != K[0]，所以继续往后移。
为了缩减篇幅，像上面那样重复移动K，直到它们的首位相同。现在要比较S[4]和K[1]。

此时S[4] == K[1]，所以继续比较下一位。

像这样继续比较下去，直到S[10]和K[6]时，S[10] != K[6]。

这时，最自然的反应就是，将K往右移动一位，然后从开头继续比较。

但是之前匹配的位置难道就没有用了吗？不，有用。
如上图所示，我们已经匹配了ABCDAB了，其中的AB是K的前缀、当前状态中S的后缀。
很自然我们就可以看出来：我们无意中已经为下一次匹配做了准备。

所以我们直接把AB对齐，下一次比较的时候，直接从AB的后一位开始比较即可。
此时S[10] != K[2]，并且已匹配的部分也没有吻合的前后缀（前、后缀不包括原字符串），所以直接跳过 3 位再进行匹配。

此处部分与第 3 ～ 5 步相似，故此处不再重复。

然后从当前这个位置匹配过去，发现全部符合。

这时，我们就找到了一个匹配的子串。位置是 15。
如果要继续寻找下一个子串，那么在记录好答案后，就是把当前状态当成失配处理，也就是把K往右移动 next[7] 位（next下文会提及），再继续找。

原理

暴力匹配的缺点

在暴力匹配中，我们是枚举子串的位置，然后判断这个子串是否等于K。这样做的时间复杂度是$O(NM)$。
但是，暴力匹配做了大量无用功，例如用上面的“暴力重复”作为例子：不用比较我们已经知道，S[5] != K[0]。为什么？因为我们上一步的匹配已经知道：S[5] = K[1] = 'B'，因为K[1] != K[0]，所以S[5] != K[0]。
那么，我们要如何利用这个信息呢？

前后缀的妙用

如上图所示，我们已经匹配的部分是ABCDAB，但是它在下一位失配了，我们能不能从已经匹配的这 6 位中寻找出一些有用的信息呢？
其中ABCDAB的后缀有：BCDAB, CDAB, DAB, AB, B，它的前缀有：ABCDA, ABCD, ABC, AB, A。为了方便，把前缀简称为数组prefix，后缀为suffix。
它们两个有什么用呢？把K往右移动k位后，suffix[k]就是S的子串的前k位，prefix[k]就是K的前k位。
这时可以发现：如果suffix[k] == prefix[k]，那就说明把K右移k位后，前k位能匹配成功。如果suffix[k] != prefix[k]，就说明把K右移k位后，S的子串与K不能匹配。
所以我们只要找出k，使suffix[k] == prefix[k]，然后把K往右移k位后，从第k+1位开始继续匹配即可。
因为这个k只与当前匹配到的K的位置有个，与S的位置无关。如果当匹配到的K的位置为j，设next[j+1]=k，那么可得以下匹配部分的代码：

int KMP_Search(const int start=0) {
    int i=start, j=0;
    while (i < n && j < m)
        if (j == -1 || str[i] == key[j]) {
            ++ i; ++ j;
        }
        else
            j = next[j];
    return (j==m)? (i-j) : -1;
}

预处理 next 数组

既然next与S无关，那么我们就可以预处理next。
当然，next也可以暴力求解，不过时间复杂度是$O(M^2)$，当K较大的时候，就会超时。

不过next可以有更快的方法。假设现在已经求得next[1~(i-1)]（因为next[0] = -1作边界，所以有效部分从 1 开始），要求next[i]（对应K[i-1]）。
如图，设k = next[i-1]，在这里k=1。因为K[k] == K[i-1]，所以直接把next往后延伸 1 位，即next[i] = k+1。

当然，更多时候K[k] != K[i-1]，这是又怎么办呢？难道要把next[i]置为 0 或 1？不，这样是错误的。在求一遍？不就变成$O(M^2)$了吗？

我们可以想：D前面接上ABCDABC是不行的，那么接短一点的可以吗？但是因为也要满足是K的前缀，所以我们可以用next[k]求出上一个符合条件的子串。
此时k = next[k] = 3，K[k] == K[i-1]，所以next[i] = k+1 = 4。否则如果K[k] != K[i-1]，那么便继续递归k = next[k]，直到K[k] == K[i-1]即可。
代码如下：

void init_KMP() {
	next[0] = -1;
	for (int i=1, k=-1; i<=m; i++) {
		while (k != -1 && key[k] != key[i-1])
			k = next[k];
		next[i] = (++ k);
	}
}

时间复杂度

要对一个算法“有谱”，那么肯定要知道它的时间复杂度。KMP 的时间复杂度分为两部分：初始化next[]、匹配子串。

初始化部分

也是直接看上面的代码，可以发现，k会递增m次，所以while只会执行m次（每执行一次k减小）。所以此处的时间复杂度为$O(M)$

匹配部分

也是直接看上面的代码，可以发现，i是一直递增的。然后j要不+1，要不j = next[j]（减小），并且当j增大的时候，i也会增大。所以j增大减小的总次数为2N。所以此处的时间复杂度为$O(N)$

综上所述，总时间复杂度为$O(N+M)$。

原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：Knuth Morris Pratt”

让我们一起看 Mao Pian 吧

概述

示例

原理