KMP 算法是一个字符串匹配算法，它的时间复杂度为 O (n+m)，其中 n 是文本的长度，m 是模式（pattern）的长度。个人觉得这应该属于是动态规划的变体。它的优势在于，当模式不匹配的时候，它可以跳过一些已经匹配过的字符，减小不必要的运算。

以下内容是对原博客的翻译：

最近几天我一直在阅读各种对 KMP（the Knuth-Morris-Pratt string searching algorithms）算法的解释。但是出于种种原因，我还是无法理解这种算法。每次我读到那句 “... 的前缀的后缀的前缀” 时，我的脑子就短路了。

最后，在我翻来覆去读了大概半小时 CLRS 的有关内容之后，我打算干脆坐下来，找点示例，再画画图。 终于，我现在理解了这个算法，也可以解释出来了。对于那些和我一样百思不得其解的读者朋友，这篇文章下面的内容都是我自己的理解。顺带提一句，我不会解释为什么这个算法比朴素的字符串匹配算法（naive string matching）要高效，与之相关 的 解释 已经有很多了，而且都很容易理解。我将会完全按照自己的理解来说明算法原理。

部分匹配表（The Partial Match Table） ​

部分匹配表是 KMP 的关键。我之前无法理解 KMP 的主要原因就在于我没有真正理解这张表里 value 的含义。现在我将尽可能用最简单的语言来解释这个表。

下面是 pattern “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 的 pattern （“abababca”），这张表就会有 8 个格子。如果我现在要填写表中的第 8 个，也就是最后一个格子，我实际上需要关注整个 pattern 。如果我要填写第七个格子，我就只需要关注 pattern 中的前 7 个字符（“abababc”），而第 8 个字符（“a”）与之无关，不需要考虑。如果我要填写第 6 个格子…… 我想你现在应该明白了。注意，我还没开始解释每个格子的含义，只是简要说明了填表的规则。

现在，为了说明格子的含义，我们首先需要知道两个概念：

• 适当前缀 ( Proper prefix )：一个字符串的所有前缀，除了整个字符串本身。比如，“S”、“Sn”、“Sna” 和 “Snap” 都是 “Snape” 的适当前缀。
• 适当后缀 ( Proper suffix )：一个字符串的所有后缀，除了整个字符串本身。比如，“agrid”、“grid”、“rid”、“id” 和 “d” 都是 “Hagrid” 的适当后缀。

（译者：原作者哈利波特粉无误😊~）

了解了这两个概念之后，我可以用一句话来解释部分匹配表中每个格子的含义：

pattern 中能够匹配到一个适当后缀的最长适当前缀的长度。

原文如下：

The length of the longest proper prefix in the (sub)pattern that matches a proper suffix in the same (sub)pattern.

我们来详细解释一下这句话。假设我们现在要填写第 3 个格子。如果你记得前文内容的话，这代表我们只关注前三个字符（“aba”）。在 “aba” 中，存在两个适当前缀（“a” 和 “ab”）和两个适当后缀（“a” 和 “ba”）。适当前缀 “ab” 没有匹配的适当后缀。但适当前缀 “a” 能匹配到适当后缀 “a”。因此，能匹配到适当后缀的最长适当前缀的长度为 1。

我们再来试试第 4 个格子。这次我们关注前四个字符（“abab”）。在 “abab” 中，存在三个适当前缀（“a”、“ab” 和 “aba”）和三个适当后缀（“b”、“ab” 和 “bab”）。这一次，“ab” 既是适当前缀也是适当后缀，长度为 2，因此第 4 个格子的值为 2。

我们再来试试第 5 个格子，即需要关注 “ababa”。我们有 4 个适当前缀（“a”、“ab”、“aba” 和 “abab”）和 4 个适当后缀（“a”、“ba”、“aba” 和 “baba”）。这一次，我们有两个匹配情况：适当前缀 “aba” 匹配到适当后缀 “aba”，适当前缀 “ab” 匹配到适当后缀 “aba”。由于 “aba” 比 “ab” 更长，因此第 5 个格子的值为 3。

让我们直接跳到第 7 个格子（也就是倒数第 2 个），需要关注 “abababc”。我们甚至都不需要穷举所有的适当前缀和适当后缀，显而易见，没有出现任何匹配的情况。所有的后缀都以字符 “c” 结尾，而所有的前缀都不以字符 “c” 结尾。因此，第 7 个格子的值为 0。

最后，我们来填写第 8 个格子，即需要关注整个 pattern ，即 “abababca”。由于 pattern 的开头和结尾都是 “a”，因此第 8 个格子的值至少为 1。然而，第 8 个格子的长度只可能是 1：当前缀和后缀的长度来到 2，所有的后缀都会包含 "c"，而适当前缀中只有 “abababc” 包含 c。这个长度为 7 的适当前缀不能匹配长度为 7 的适当后缀，因此第 8 个格子的值为 1。

怎么使用部分匹配表 ​

（译者：原作者这里将匹配两个字符串： text 和 pattern ，用这样一个具体的例子来解释部分匹配表的跳转方法）

在我们找到部分匹配的字符串时，我们可以利用部分匹配表中的值来跳过一些字符（而不是重复进行一些比较）。公式如下：

如果我们找到了一个部分匹配，其长度为 partial_match_length，且 table[partial_match_length] > 1 ，我们就可以直接跳过 partial_match_length - table[partial_match_length - 1] 个字符。

例如，假设我们想要用 pattern “abababca” 来匹配 text “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

这次部分匹配的长度为 1。 table[partial_match_length - 1] （即 table[0] ）的值为 0，因此我们不能跳过任何字符。下一次部分匹配出现在这里：

bacbababaabcbab
    |||||
    abababca

这次部分匹配的长度为 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

这次部分匹配的长度是 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

匹配到这里，我们的 pattern 长度已经比 text 的剩余长度要长了，所以我们知道接下来不可能会有任何完全匹配了。

结论 ​

那么现在你应该懂了。就像我之前承诺的，这篇文章不是什么详尽的解释，也不是对 KMP 的正式证明。它就像是在我脑海里漫步，把我之前感到困惑的部分用详细地说了出来。要是你还有什么疑问，或者发现文章里有什么错误，请在评论区留言（译者：🚀 again，原作者的评论区见原文），也许我们都可以从中学到什么。