【算法】查找字符串的 KMP 算法

“在一个字符串S中查找一个词W出现的位”是一道常见的面试题。

相对于那些要对树、图进行操作的算法，这个算法要处理的是一维线性的字符序列。看起来似乎简单不少，那么算法难度会更低吗？让我们来看看。

简单直接的字符串查找算法

算法原理

首先，如果只是笼统地从一个字符串中查找另一个字符串，有一种很直接的方法，那就是：

• 从 S 的第 1 个字符开始，与 W的每一个字符一一匹配。
  • 如果一致，就继续匹配下一个，如果w的所有字符都匹配上了，则说明已经查找到了W。
  • 如果不一致，则从S的第 2 个字符开始重复整个过程；如果还不行就再从第三个字符开始……总之就是跳回到本次匹配S开始处的下一个字符，然后重新开始整个匹配过程
• 如果到最后都没有匹配上完整的W，则说明S中根本无法找到 W。

算法流程图

本算法流程图如下：

算法运行示例

按照它进行字符串查找的案例如下：

算法性能

这个算法又简单又好操作，唯一的缺点是有点慢。

假设 S 的长度为 n 而 W的长度为 m，则这个直接算法的时间复杂度是 O(n*m)。

有没有效率更高的，时间复杂度类似 O(n)的算法呢？还真的有，这个算法的名字叫做 KMP算法。

高效率的 KMP 算法

算法历史

K, M, P 这三个字母是本算法的三位发明人名字的缩写，这三位是：Knuth (大名鼎鼎的高德纳)，Morris，和 Pratt。三人于1977年联合发表了该算法。

对直接匹配法的改进

前面直接匹配算法中，为什么每次匹配失败后，重新开始匹配后S上的基点都只是相较上一次后移一个位置，而不是将之前匹配过的部分都跳过呢？

比如上面的例子，为什么不能像下面这样运行呢？

这样看起来也挺好嘛。如果把匹配过的都跳过去，那整个算法的时间复杂度不就变成 O（n）了吗？

改进引出的错误

为什么不跳？那是因为，如果这么跳的化就会出现下面这样的情况：

假设我们在"ababababcdcd" 中查找"abababc"。

第一轮匹配我们就能匹配上6个字符。如果第二轮匹配我们一下子就跳过这 6 个字符，直接从s 的第7个字符开始，那最终的结果肯定是从 s 中无法查找到w ——

Round 1

s: ababababcdcd

w: abababc

Round 2

s: ababababcdcd

w: abababc

Round 3

s: ababababcdcd

w: abababc --> Fail

而如果一个个字符向后挪，则会在 s 的第三个字符处匹配上 w ——

Round 1

s: ababababcdcd

w: abababc

Round 2

s: ababababcdcd

w: ababbabc

Round 3

s: ababababcdcd

w: abababc --> Success

这是为什么呢？

大家仔细看，w 的前 6 个字符是 ababab，这 6 个字符，除了和 s 中第 1 到第 6 个字符匹配，还和第 3 到第 8 个字符匹配，这两次匹配中，s 中的一段区间，也就是第 3 到第 6 个字符是重合的：

Round 1 -- s: ababababcdcd

Round 2 -- s: ababababcdcd

重合的这段字符 “abab” 和匹配上的那段字符 “ababab” 之间，又是什么关系呢？

简单而言，abab 既是 ababab 的前缀，又是 ababab 的后缀，这就是它们之间的关系。

字符串的前缀和后缀

这里要解释一下字符串的前缀和后缀。

如果字符串 A 和 X，存在 A = XB，其中 B 是任意的非空字符串，那就称 X 为A的前缀。所有前缀构成前缀集合。

例如，“Great”的前缀有：“G”, “Gr”, “Gre”, 和 “Grea”，它的前缀集合: {“G”, “Gr”, “Gre”, “Grea”}。

反之，如果字符串 A 和 X 存在 A = BX，其中 B 是任意的非空字符串，那就称 X 为 A 的后缀。所有后缀构成后缀集合。

“Great” 的后缀集合为：{“reat”, “eat”, “at”, “t” }。

前后缀集合交集中的最长元素

那我们来看看ababab。它的前缀集合是：{“ababa”, “abab”, “aba”, “ab” , “a”}；而它的后缀集合为：{“babab”, “abab”, “bab”, “ab”, “b”}。

我们看这两个集合的并集为 {“abab”, “ab”}，而显然 “abab” 比 “ab” 要长，那么也就是说 “ababab” 这个字符串的子字串 “abab” 同时是原字串的前缀和后缀，而且是所有满足这一条件的子字串中最长的那个。

此时我们回到原题，在 s：“ababababcdcd” 中查找 w：“abababc”。

第一次匹配前 6 个字符都相符，而第 7 个字符不符时，我们就要将 w 向后移动了。

s: ababababcdcd

w: abababc

这个时候，如果我们已经知道了刚刚匹配上的 6 个字符 “ababab” 有一个子字符串 “abab” 是 s 中匹配中的前 6 个字符组成的字串的后缀，而偏偏又是 w 中前 6 个字符组成字符串的前缀！

那么在下次匹配的时候，我们怎么能一下跳到刚巧在 s 中重用这几个字符（“abab”）的位呢？

首先我们知道现在错配的位置为第 7 个字符，如果整个跳过已经匹配的字符下一次就该从第7个字符开始，但是因为我们要重用前 6 个字符的一部分，因此要退回来一段。

那一段有多长呢？就是就是 “abab” 的长度：4！下次我们不是从第 7 个字符，而是再往前退 4 步，从第 3 个字符开始下一轮匹配。如此，就找到 w 了。

这次是匹配上了6个字符，那如果只匹配上了5个或者4个呢？

同理，我们只要知道匹配上的那个字符串的前后缀交集中最长的子字串长度，在下次移动时重用这个最长前缀兼后缀就好了。

Partial Match Table (PMT)

综上，我们需要做的就是将 w 的所有前缀罗列出来，然后分别统计这一个个前缀字符串的前缀集合与后缀集合并集中子串的最大长度，我们把这个长度称为 Partial Match Value，简称 PM Value。

比如当前这个 w，它一共有6个前缀: “ababab”, “ababa”, “abab”, “aba”, “ab”, 和 “a”。

我们分别统计这 6 个字符串的 Partial Match Value —— 前后缀交集中元素长度的最大值。

刚才已经计算了Partial Match Value对于“ababab”而言是4，对于 “ababa” 而言，是3 （对应子串为 “aba”），“abab” 而言是2（对应子串为 “ab”），对于 “aba” 而言是1（对应 “a”）。而“ab”的前后缀没有交集，“a”干脆没有前后缀，于是他们俩的 Partial Match Value 为 0。

我们可以把这些值放在一个表格（Table）里面，以供查询，这个表格就叫做 Partial Match Table（缩写为PMT），下面就是 “abababc” 的PMT：

Partial Match Table，PMT

计算出了 PMT 之后，我们就可以进入到 KMP 算法了。

KMP 算法详解

算法原理

其实，KMP算法可以用我们前面说的直接算法来套用：

• 从 s 的第 1 个字符开始，与 w 的每一个字符一一匹配。
  • 如果一致，就继续匹配下一个，如果 w 的所有字符都匹配上了，则说明已经查找到了 w。
  • 当 s 和 w 的字符不一致的时候，我们回到 s 起始处然后要往下走若干步，具体走多少步呢？首先我们要确定已经匹配上的子串的长度——
    • 如果 s 和 w根本一个字符都没有匹配上，那就完全和直接算法一样，s 前进一步，w 回到开头，重新开始
    • 如果已经匹配上的字符数量 >= 1，那么我们就要在 PMT 中查找已经匹配上的子串的最后一个字符对应的 PM value，用匹配字串的长度减掉 PM value 的值，就是 s 前进的步数。
    • s 前进后w也回到首字符，重新开始匹配。
• 如果到最后都没有匹配上完整的 w，则说明 s 中根本无法找到 w。

算法流程图

下图是 KMP 算法的流程图：

与直接算法的对比

我们横向对比一下直接查找字符串算法和 KMP 算法，会发现，其实就是紫色框内的部分不同而已。

算法性能

KMP 算法的时间复杂度是 O(n+m)，因为正常情况下m 小于等于n，因此 O（n+m) 也就是 O(n).

两种算法的编程实现

直接匹配算法

有了流程图，我们来实现代码就容易多了，我们可以先从直接匹配算法开始：

KMP 算法

对应的 KMP 算法代码如下：

PMT 的生成

要注意一点，对于 KMP 算法本身而言，我们把 PMT 作为已知条件，在代码中 PMT 作为算法函数的输入参数直接传入。

在面试的时候，一般不需要写 PMT 的生成部分，毕竟考察的是 KMP 算法。

当然，如果真的要运行程序，还是需要现针对 w 生成 PMT 的。这部分代码大家可以到 github文件中查看。

完整代码和数据请见：

https://github.com/juliali/ClassicAlgorithms/tree/main/str_match