KMP算法理解

KMP算法理解

KMP算法主要用于字符串匹配。

本文主要是针对http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/的翻译和自己的理解，并没有额外的理论理解。

匹配表

匹配表这个翻译不算准确，原文为 The Partial Match Table即部分匹配表。这个表也是整个算法的核心。

下面以一个例子来具体讲解一下这个表，

这里我们有一个字符串“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 |

我们得到上面的匹配表，

首先表分为3行，分别为char，index，value。每个字符为一列，本例共8列。

第一第二行很好理解，就是每个字符以及它在字符串中对应的位置（从0开始）

在开始讲解value行，需要先拓展2个概念，即合理前缀（proper prefixes）和合理后缀（proper suffixes）。

合理前缀：即尾部切去部分字符的剩余，例如 “S”, “Sn”, “Sna”, 以及“Snap” 都是”Snape“的合理前缀。

合理后缀：与前缀概念相反，即首部切去部分的剩余，  “agrid”, “grid”, “rid”, “id”, and “d” 是“Hagrid”的合理后缀。

下面引出一句比较绕口的定义：

“pattern中合理前缀与合理后缀相同的集合中，最长的前缀（后缀）的长度”

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

比如我们看第三列，我们截取aba，aba有2个合理前缀即a和ab，2个合理后缀a和ba，他们的交集为a，那么最长的匹配为1，因此value行的第三列的值为1。

第4列截取，abab，合理前缀为a,ab,aba, 合理后缀为b,ab,bab, 交集为{a, ab},最长为2，因此第四列为2.

依次类推我们可以得出全部的匹配表

使用匹配表

使用匹配表可以帮助在字符串匹配过程跳过一些反复匹配的过程，提高匹配效率。

公式是这样的：

如果部分匹配的长度不为0(partial_match_length->pmt)，且匹配表中对应的该匹配长度的值大于1（table[partial_match_length]>1 ->t[pmt-1])，我们可以向前跳过partial_match_length-table[partial_match_length-1] ( pmt-t[pmt-1])个字符。

举例来说，我们需要在“bacbababaabcbab”，寻找”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 |

第一次匹配到

bacbababaabcbab
 |
 abababca

这里匹配到的长度为1,

pmt=1,  t[pmt-1] = t[1-1] = t[0] = 0, 我们不能跳过任何字符

接着匹配到

bacbababaabcbab
    |||||
    abababca

pmt = 5, t[pmt-1] = t[5-1]=t[4] = 3

pmt-t[pmt-1] = 5-3= 2

可以跳过2个字符，

// x denotes a skip

bacbababaabcbab
    xx|||
      abababca

接着匹配到长度为3的字符串aba

pmt=3

t[pmt-1]=1

可跳过3-1=2个字符串

// x denotes a skip

bacbababaabcbab
      xx|
        abababca

现在匹配字符长度超过了剩下的字符，可以总结目标字符串中不包含我们的pattern。