通俗演绎KMP

最近要实现关键字过滤功能,小看了一些经典的字符串匹配算法。
本文要介绍的是KMP算法(Knuth–Morris–Pratt Algorithm),那个Knuth应该再熟悉不过了。

KMP算法是从朴素匹配算法改进而来。回忆一下朴素的匹配算法是怎么完成字符串的匹配的呢?
1. 将原串和模式串左对齐,然后一位一位比较,直到有一个字符不匹配
KMP1.png
2. 发现第二位的B和C不匹配,模式串右移一位
KMP2.png
3. 重复这个流程,直到找到完全匹配的子串或者匹配失败。

但这过程中显然有多比较的地方。如,原串为ABCDEABCDF,模式串为ABCDF。第一轮可以发现E和F不匹配
KMP3.png
很显然右移一位必定不匹配,这时模式串可以直接右移4位跳过ABCD,从E开始再次比较
KMP4.png

那是不是跳过的长度就是前面相同部分的长度呢?其实不是这样的,这种直接跳过前面相同部分的做法在某些情况下会有问题。如,原串为ABCDABCDABF,模式串为ABCDABF,直接跳过相同部分就会遗漏匹配的串
KMP5.png
所以跳过的长度并不是前面完全匹配的部分,可以跳过的长度一般存储在模式串的partial match table中,即KMP算法需要对模式串进行预处理。

先来看看这个partial match table在跳过的过程中是怎么用的,然后再来考察计算partial match table的算法。
ABCDABF的partial match table如下:
KMP6.png
可以跳过的长度 = 当前已匹配长度 - 最后一个字母在partial match table中的值。例如:
KMP7.png
当发现C和F不匹配时,根据公式,当前已匹配串ABCDAB长度为6, 最后一个字母B在partial match table中的对应值为2,所以可以跳过的长度 = 6 - 2 = 4,即:
KMP8.png
这样就能正确匹配了。

partial match table中每个位置i记录的其实就是从0到i的子串中,同时出现在子串前缀和后缀中的最大长度。还是以上面那个例子为例:

  • A没有前缀或后缀,所以长度为0
  • AB前缀为A,后缀为B,没有相同部分,长度为0
  • ABC前缀为A、AB,后缀为BC、C,没有相同部分,长度为0
  • ABCD前缀为A、AB、ABC,后缀为BCD、CD、D,没有相同部分,长度为0
  • ABCDA前缀为A、AB、ABC、ABCD,后缀为BCDA、CDA、DA、A,相同部分为A,长度为1
  • ABCDAB前缀为A、AB、ABC、ABCD、ABCDA,后缀为BCDAB、CDAB、DAB、AB、B,相同部分为AB,长度为2
  • ABCDABF前缀为A、AB、ABC、ABCD、ABCDA、ABCDAB,后缀为BCDABF、BCDAB、CDAB、DAB、AB、B,没有相同部分,长度为0

具体代码参考https://github.com/hbprotoss/codejam/blob/master/kmp.py

全文完。

Comments

Comments powered by Disqus