KMP算法精解及其Python版的代码示例
KMP算法是经典的字符串匹配算法，解决从字符串S，查找模式字符串M的问题。算法名称来源于发明者Knuth，Morris，Pratt。
假定从字符串S中查找M，S的长度ls，M的长度lm，且（ls>lm）。
朴素的字符串查找方法
从字符串S的第一个字符开始与M进行比较，如果匹配失败。从下一字符开始，重新比较。指导第(ls-lm)个字符。
这种方法容易想到并且容易理解，效率不高。
问题在于每次匹配失败后，移动的步伐固定为1，其实步子可以迈得再大一些。
KMP的字符串查找方法
假定在模式串的连续字串M[0,i]且i<lm，已经成功匹配字符串S。但是不巧第i+1个字符失败了，怎么办？移动一个字符，重头再来？当然不好，那就是朴素路线了。我们能否从跌倒的地方继续走呢？
既然字串M[0-i]已经匹配成功，那就从这个子串上做文章。举个栗子
此时匹配失败在M串的第5个字符，前4个字符已经匹配成功。
如果从跌倒的地方出发，则需要存在M[0,4]的子串M[0,k]==S[j+4-k,j+4]。
由于M[0,4]==S[j, j+4]则有字串S[j+4-k,j+4]==M[4-k,4]。综上有M[0,k]==M[4-k,4]
如果这样的k不存在，那就老老实实的朴素了。
从上面的表格可以直观的看出，下一次匹配只要把M串移动到j+3位置，从j+5开始匹配就可以。很容易看出来在已经匹配成功的字串M[0,4]中有最长的子串（M[0,1]==M[3,4]），这个就是问题的关键。
因此KMP的核心部分就是计算模式串的各个子串的k。
实例
首先我们来看一下字符串的朴素匹配.
可以想象成把文本串s固定住,模式串p从s最左边开始对齐,如果对齐的部分完全一样,则匹配成功,失败则将模式串p整体往右移1位,继续检查对齐部分,如此反复.
#朴素匹配 defnaive_match(s,p): m=len(s);n=len(p) foriinrange(m-n+1):#起始指针i ifs[i:i+n]==p: returnTrue returnFalse
关于kmp算法,讲的最好的当属阮一峰的<字符串匹配的KMP算法>.一路读下来,豁然开朗.
其实就是,对模式串p进行预处理,得到前后缀的部分匹配表,使得我们可以借助已知信息,算出可以右移多少位.即kmp=朴素匹配+移动多位.
更多细节请看阮一峰的文章,这里就不展开了.
下面给出python的代码实现.
#KMP
defkmp_match(s,p):
m=len(s);n=len(p)
cur=0#起始指针cur
table=partial_table(p)
whilecur<=m-n:
foriinrange(n):
ifs[i+cur]!=p[i]:
cur+=max(i-table[i-1],1)#有了部分匹配表,我们不只是单纯的1位1位往右移,可以一次移动多位
break
else:
returnTrue
returnFalse
#部分匹配表
defpartial_table(p):
'''''partial_table("ABCDABD")->[0,0,0,0,1,2,0]'''
prefix=set()
postfix=set()
ret=[0]
foriinrange(1,len(p)):
prefix.add(p[:i])
postfix={p[j:i+1]forjinrange(1,i+1)}
ret.append(len((prefix&postfixor{''}).pop()))
returnret
printnaive_match("BBCABCDABABCDABCDABDE","ABCDABD")
printpartial_table("ABCDABD")
printkmp_match("BBCABCDABABCDABCDABDE","ABCDABD")