不是播放器，是一个巨牛X的字符串算法——KMP

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

今天我们一起来聊聊一个非常经典的字符串匹配算法——KMP。

KMP简介

KMP乍一听像是某播放器的名字，仔细一看像是看毛片的缩写……但其实，它是取自发明该算法的三个大佬的名称缩写：让我们记住这三位大佬，他们分别是Knuth、Morris、Pratt。

本人的KMP算法学自著名大牛Matrix67的博客，大家感兴趣也可以移步大佬的博客。

大佬在博客当中有一句著名的骚话，当你有一个喜欢的MM，你可以委婉地问她：“假如你要向你喜欢的人表白的话，我的名字是你的告白语中的子串吗？”

这句骚话点名了KMP算法的使用场景——字符串匹配。它可以在

的时间复杂度内快速判断两个字符串是否有包含关系。比如A串是：I hate learning English. B串是hate learning，很明显B串是A串的子串。但是如果我们要设计算法去进行判断的话，由于A串中的任何一个位置都有可能是B串的开头，所以在传统方法当中我们要枚举A串中的所有位置进行尝试。

这样一来整体的复杂度就是

，其中

和

分别是AB两个字符串的长度。显然，在两个字符串很长时，这是不可接受的。

在这种情况下就需要KMP算法出场了，它代码实现简单，也不需要借助很大的辅助空间就可以实现字符串的快速匹配。

原理框架

KMP算法和传统算法在执行过程当中有一个很大的区别，朴素的暴力解法枚举的是A串的起始位置能够和B串匹配上的长度。如果匹配上的长度刚好等于B串的长度，那么说明B串是A串的子串。

而KMP的逻辑则有些不同，KMP算法同样会枚举A串的每一个位置，但A串枚举出的位置是作为结尾使用的，我们关心的是以当前枚举的这个字符结尾的后缀和B串前缀匹配上的长度，如果这个长度等于B串的长度，那么同样认为找到了一个匹配。

我们用编程语言再来描述一下这个过程，我们用i表示当前枚举到的A串的位置。我们寻找的是i对应的最大j，使得A[i-j+1: i]能和B[:j]相等。其实和枚举的逻辑是一样的，只不过对于A串而言，枚举的方法是向后匹配，KMP是向前匹配。

那为什么KMP要做这么一个逻辑上的改动呢？我们来看这么一个例子：

虚线框出来的位置出现了不匹配的情况，那么我们要重新找一个B串的前缀和A串匹配。由于B串中D这个字母之前的位置是和A串匹配上的，假设我们找到了一个匹配的前缀，那么这个前缀除了最后的字母是C以外应该也能和D之前匹配上。

我们肉眼观察可以在B串中找到这么一个ABC的前缀可以和A串当前位置匹配上，如下图：

这个ABC的前缀和B串刚刚匹配的ABD的位置，除了最后一个字母之外，其余部分都是匹配的。这个匹配以及查询的过程只和B串有关，其实和A串是没有关系的。既然和A串无关，那么我们就可以事先预处理好，从而实现快速查找。

这个事先预处理好的数组就叫做next数组，或者失败数组。

next数组

next数组是干嘛的呢？其实和刚才的逻辑一样，存储的是后缀和前缀的最大匹配长度。

next[i]表示B串当中以i这个位置结尾的后缀能够和B串前缀匹配上的最大长度。比如刚刚那个例子当中，B串是ABCDABD，对应的next数组就是[0, 0, 0, 0, 1, 2, 0]。

数组当中1和2的来源，就是从上图划线处来的。

有了next数组之后，在每次枚举失败时，假设当前B串的下标是j。那么我们只需要寻找next[j-1]的值，来尝试B[next[j-1]]+1的位置是否能够和A[i]构成匹配。如果还失败，那么继续往前寻找下一个next的位置，直到遇到0为止。

有了next数组之后， 我们就可以写出匹配的逻辑了。这里我们为了处理方便，将字符串的下标向右移动了一位，字符串的下标都从1开始。

int j = 0;
for (int i = 1; i < n; i++) {
    while (j > 0 && A[i] != B[j+1]) {
        j = next[j];
    }
    if (s[j+1] == s[i]) j++;
    if (j == B.size()) matched = true;
}
matched = false;

求解next数组

到这里，问题只剩下了一个，就是这个next怎么来呢？

如果我们从逻辑出发的话，会发现next数组的逻辑和我们刚才执行匹配的逻辑是一样的。本质上都是寻找的最大后缀与前缀匹配的长度，上面的代码我们执行的是A串与B串的匹配，构造next数组其实就是B串的自匹配。

比较trick的地方在于当我们求解next[i]时，其实可以利用next[i-1]的结果。因为next[i-1]求出了以i-1位置得到的最大前缀匹配，那么我们只需要在此基础上判断A[i] == A[next[i-1]+1]是否匹配即可，如果匹配，那么next[i] = next[i-1]+1。否则，我们再寻找next[next[i-1]]，直到为0。

我们写出代码，会发现和上一段代码非常相似：

int j = 0;
// 这里是从2开始
for (int i = 2; i < n; i++) {
    j = next[i-1];
    while (j > 0 && A[i] != B[j+1]) {
        j = next[j];
    }
    if (s[j+1] == s[i]) j++;
    next[i] = j;
}

这样一来，我们只要把上下这两段代码整合在一起，就算是完整地实现了KMP算法了。

KMP算法开创性地使用后缀匹配代替了前缀匹配，并由此构建了next数组，这个思想后来发扬光大衍生了很多其他算法，比如多字符串匹配的AC自动机等。

一般来说应付常规的LeetCode周赛或者是面试，KMP算法就足够使用了。对于初学者来说里面的很多思路以及代码可能会不太直观，一次看完很难完全领会。这是非常正常的，看完一遍不懂就多看几遍，代码写过一次很生疏就多写几次。刻意的反复练习是学习尤其是算法学习的必经之路。