我理解的 KMP 算法

balala

最近一段时间，我一直在看 KMP 字符串模式匹配算法的各种不同解释。因为各种原因，没有找到一种我觉得好的解释。当我读到“……的前缀的后缀的前缀”时，我会不停地拍自己的脑袋。

最后，花了大约30分钟将《算法导论》里相同的部分反反复复读了以后，我决定坐下来做一些例子和图解。现在，我已经搞清楚了这个算法并能对它解释。对于那些和我有一样想法的人，下面是我自己的理解。一方面，我不打算解释为什么它比朴素的字符串匹配效率更高；这些在很多地方都已经解释得非常好了。我要说明的是，它究竟是如何工作的。

部分匹配表

毫无疑问，KMP算法的精髓是部分匹配表。我理解KMP算法时，最大的障碍就在于是否充分明白部分匹配表里的值所代表的意义。下面我会尽可能简单地来解释这些。

下面这个是“abababca”这个模板的部分匹配表：

char: | a | b | a | b | a | b | c | a |

index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |

value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

如果我有一个8个字符的模板（这里我们就用“abababca”来举例子），我的部分匹配表将会有8格。如果此时此刻我正匹配模板的第8格即最后一格，那意味着我匹配了整个模板（“abababca”）；如果我正匹配模板的第7格，则意味着当前仅匹配了整个模板的前7位（“abababc”），此时第8位(“a”)是无关的，不用去管它；如果我此时此刻正匹配模板的第6格，那意味着……看到这里你应该已经明白我的意思了。目前我还没有提到部分匹配表每格数据的含义，在这里仅仅是交代了大概。

现在，为了说明刚刚提到的每格数据的含义，我们首先要明白什么是最优前缀什么是最优后缀。

最优前缀：一个字符串中，去除一个或多个尾部的字符所得的新字符串就是最优前缀。例如 “S”、 “Sn”、 “Sna”、 “Snap”都是“Snape”的最优前缀。

最优后缀：一个字符串中，去除一个或多个首部的字符所得的新字符串就是最优后缀。例如“agrid”、 “grid”、“rid”、 “id”、“d”都是 “Hagrid”的最优后缀。

有了两个概念，我现在可以用一句话来概括部分匹配表里每列数据的含义了：

模板（子模板）中，既是最优前缀也是最优后缀的最长字符串的长度。

下面我举例说明一下这句话。我们来看部分匹配表的第3格数据，如果你还记得我在前面提到的，这意味着我们目前仅仅关心前3个字母（“aba”）。在“aba”这个子模板中，有两个最优前缀（“a”和“ab”）和两个最优后缀（“a”和“ba”）。其中，最优前缀“ab”并不是最优后缀。因此，最优前缀与最优后缀中，相同的只有“a”。那么，此时此刻既是最优前缀也是最优后缀的最长字符串的长度就是1了。

我们再来试试第4格，我们应该是关注于前4个字母（“abab”）。可以看出，有3个最优前缀（“a”、“ab”、 “aba”）和3个最优后缀（“b”、“ab”、“bab”）。这一次 “ab” 既是最优前缀也是最优后缀，并且长度为2，因此，部分匹配表的第4格值为2。

这是很有趣的例子，我们再看看第5格的情况，也就是考虑“ababa”。我们有4个最优前缀（“a”、 “ab”、“aba”，和“abab”）和4个最优后缀（“a”、 “ba”、“aba”，和“baba”）。现在，有两个匹配“a”和“aba” 既是最优前缀也是最优后缀，而“aba”比“a”要长，所以部分匹配表的第5格值为3。

跳过中间的直接来看第7格，此时只考虑字母“abababc”。即使不一一枚举出所有的最优前缀与最优后缀也不难看出，这两个集合之间不会有任何的交集。因为，所有最优后缀都以“c”结尾，但没有任何最优前缀是以“c”结尾的，所以没有相匹配的，因此第7格值为0。

最后，让我们看看第8格，也就是考虑整个模板（abababca）。它的最优前缀与最有后缀都以“a”开头以“a”结尾，所以第8列的值至少是1。然而1就是最终结果了，所有长度大于等于2的最优后缀都包含“c”，但只有“abababc”这一个最优前缀包含“c”，这个7位的最优后缀“bababca”并不匹配，所以第8列最终赋值为1。

如何使用部分匹配表

当我们找到了部分匹配的字符串时，可以用部分匹配表里的值来跳过前面一些字符（而不是重复进行没有必要的比较）。具体是这样工作的：

如果已经匹配到的部分字符串的长度为partial_match_length且 table[partial_match_length] > 1，那么我们可以跳过partial_match_length- table[partial_match_length - 1]个字符。

比如，我们拿“abababca”来这个模板来匹配文本“ bacbababaabcbab”的话，我们的部分匹配表应该是这样的：

char: | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

第一次匹配的时候是在这里

bacbababaabcbab
|
abababca

partial_match_length值为1，对应的table[partial_match_length - 1] （即table[0]）值为0。所以，这种情况下我们不能跳过任何字符。下一次的匹配是这里：

bacbababaabcbab
|||||
abababca

partial_match_length值为5，对应的 table[partial_match_length - 1] （即 table[4]）值为3。这意味着我们可以跳过 partial_match_length- table[partial_match_length - 1] （即 5 – table[4] 或5 – 3 亦即 2）个字符：

// x 表示一个跳过

bacbababaabcbab
xx|||
abababca

partial_match_length值为3，对应的 table[partial_match_length - 1] （即 table[2]）值为1，这意味着我们可以跳过 partial_match_length- table[partial_match_length - 1] （即 3- table[2] 或3 – 1亦即 2）个字符：

// x 表示一个跳过

bacbababaabcbab
xx|
abababca

现在，模板长度大于所剩余的目标字符串长度，所以我们知道不会再有匹配了。

结语

那么你应该搞明白了吧。就像我一开始说的，这篇文章没有关于KMP多余的解释或者或枯燥的证明；而是我自己的理解，以及我发现的容易让人感到迷惑部分的详尽解释。如果你有任何疑问或者发现我这篇文章哪里写错了，请给我留言；也许我们都会有所收获。