KMP 算法
字符串匹配有很多算法可以实现,Knuth-Morris-Pratt 算法(简称KMP)是最常用的之一,时间复杂度为 O(m+n)
,其中 m
为模式串的长度,n
为目标串的长度。
KMP 算法的核心为部分匹配表 PMT(Partial Match Table),在理解 PMT 之前,需要先了解字符串的前缀与后缀分别指什么。
- 前缀:对于字符串
A
和B
,若存在任意非空字符串S
,使得A=BS
,则称B
为A
的前缀。如hello
的前缀集合为[hell, hel, he, h]
- 后缀:对于字符串
A
和B
,若存在任意非空字符串S
,使得A=SB
,则称B
为A
的后缀。如hello
的后缀集合为[ello, llo, lo, o]
那么,PMT 中的值即为当前位置字符串的前缀集合与后缀集合中公共元素的最大长度。比如字符串 ababa
的 PMT 值为 2,因为前缀集合为 [abab, aba, ab, a]
,后缀集合为 [baba, aba, ba, a]
,公共元素为 aba
与 a
,最大长度为 2。
如何使用 PMT 来加速字符串的匹配呢?
对于字符串 ababababca
与 模式串 abababca
,我们首先给出模式串的 PMT 数组:
开始匹配时,会在下图红色位置匹配失败,这时需要回溯,普通方法直接令 i=1, j=0
从头开始匹配,这样复杂度极高,KMP 算法利用模式串 PMT 数组的特性,可以回溯到指定位置而减少一部分不必要的匹配。
我们目前有以下两点信息:
- 由图可以知道
j
位置之前的pattern
部分 与i
位置之前的string
同长度部分是完全相同的(用灰色底色显示); - 此时
j
位置之前的pattern
部分字符串 PMT 值为 4,说明此子串前四个字母和后四个字母完全相同。
结合这两点可知,i
位置之前长度为 4 的子串与 pattern
开头的长度为 4 的子串完全相同。那这部分直接跳过,匹配下一个位置即可!!如下图:
综上,每次失配时只需要回溯到 pattern
当前位置的上一个位置的 PMT 值的位置开始匹配就可以,那么将 PMT 数组统一向右移一位得到 next
数组,表示当前位置失配时需要回溯的目标位置,即:
最开始的位置补 0 只是为了写代码方便,用来指示已经回溯到 pattern
串的开头位置了。
Python 代码
1 | class KMP(object): |
参考
https://www.zhihu.com/question/21923021/answer/281346746
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html