什么是KMP?

部分匹配表

当然，KMP 的关键是部分匹配表。我和理解 KMP 之间的主要障碍是我没有完全理解部分匹配表中的值的真正含义。我现在将尝试用最简单的词来解释它们。

这是模式“abababca”的部分匹配表：

1 
2 
3

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 个单元格。如果我查看表格中的第八个也是最后一个单元格，我会对整个模式（“abababca”）感兴趣。如果我查看表格中的第七个单元格，我只对模式中的前七个字符 (“abababc”) 感兴趣；第八个（“a”）无关紧要，可以从建筑物或其他东西上掉下来。如果我正在查看表格中的第六个单元格……您就会明白。请注意，我还没有讨论每个单元格的含义，而只是讨论它所指的内容。

现在，为了谈论含义，我们需要了解适当的前缀和适当的后缀。

适当前缀：字符串中的所有字符，其中一个或多个字符被剪掉。“S”、“Sn”、“Sna”和“Snap”都是“Snape”的正确前缀。

适当的后缀：字符串中的所有字符，以一个或多个开头。“agrid”、“grid”、“rid”、“id”和“d”都是“Hagrid”的正确后缀。

考虑到这一点，我现在可以给出部分匹配表中值的一句话含义：

（子）模式中与同一（子）模式中的适当后缀匹配的最长适当前缀的长度。

让我们来看看我的意思。假设我们正在查看第三个单元格。正如您在上面会记得的那样，这意味着我们只对前三个字符（“aba”）感兴趣。在“aba”中，有两个适当的前缀（“a”和“ab”）和两个适当的后缀（“a”和“ba”）。正确的前缀“ab”与两个正确的后缀中的任何一个都不匹配。但是，正确的前缀“a”与正确的后缀“a”匹配。因此，在这种情况下，与适当后缀匹配的最长适当前缀的长度为 1。

让我们为单元格四尝试一下。在这里，我们对前四个字符（“abab”）感兴趣。我们有三个适当的前缀（“a”、“ab”和“aba”）和三个适当的后缀（“b”、“ab”和“bab”）。这一次，“ab”在两者中，并且是两个字符长，因此单元格 4 的值为 2。

正因为它是一个有趣的例子，让我们也为单元格 5 尝试一下，它涉及“ababa”。我们有四个适当的前缀（“a”、“ab”、“aba”和“abab”）和四个适当的后缀（“a”、“ba”、“aba”和“baba”）。现在，我们有两个匹配项：“a”和“aba”都是正确的前缀和正确的后缀。由于“aba”比“a”长，所以它获胜，并且单元格 5 获得值 3。

让我们跳到第 7 个单元格（倒数第二个单元格），它与模式“abababc”有关。即使没有列举所有正确的前缀和后缀，很明显不会有任何匹配；所有的后缀都以字母“c”结尾，而没有一个前缀。由于没有匹配项，单元格 7 为 0。

最后，让我们看看单元格 8，它与整个模式（“abababca”）有关。由于它们都以“a”开头和结尾，因此我们知道该值至少为 1。然而，这就是它结束的地方；在长度为 2 及以上时，所有后缀都包含 ac，而只有最后一个前缀（“abababc”）包含。此七字符前缀与七字符后缀（“bababca”）不匹配，因此单元格 8 为 1。

如何使用部分匹配表

当我们找到部分匹配时，我们可以使用部分匹配表中的值跳过（而不是重新进行不必要的旧比较）。该公式的工作原理如下：

如果找到长度为partial_match_length的部分匹配并且table[partial_match_length] > 1，我们可以跳过partial_match_length - table[partial_match_length - 1]字符。

假设我们将模式“abababca”与文本“bacbababaabcbab”进行匹配。这是我们的部分匹配表，以供参考：

1 
2 
3

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 |

我们第一次获得部分匹配是在这里：

1 
2 
3

bacbababaabcbab
 |
 abababca

这是一个partial_match_length 为1。table[partial_match_length - 1]（或table[0]）处的值是0，所以我们不会跳过任何。我们得到的下一个部分匹配在这里：

1 
2 
3

bacbababaabcbab
    |||||
    abababca

这是 5 的 partial_match_length。table[partial_match_length - 1](or table[4])处的值是 3。这意味着我们可以跳过partial_match_length - table[partial_match_length - 1](or5 - table[4]或5 - 3or 2) 字符：

1 
2 
3 
4 
5

// x denotes a skip

bacbababaabcbab
    xx|||
      abababca

这是 3 的 partial_match_length。table[partial_match_length - 1](or table[2])处的值是 1。这意味着我们可以跳过partial_match_length - table[partial_match_length - 1](or3 - table[2]或3 - 1or 2) 字符：

1 
2 
3 
4 
5

// x denotes a skip

bacbababaabcbab
      xx|
        abababca

此时，我们的模式比文本中剩余的字符长，因此我们知道没有匹配项。