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，原作者的评论区见原文），也许我们都可以从中学到什么。