KMP算法精解及其Python版的代码示例
发布时间：2020-12-16 20:39:36 所属栏目：Python 来源：网络整理
导读：KMP算法是经典的字符串匹配算法，解决从字符串S，查找模式字符串M的问题。算法名称来源于发明者Knuth，Morris，Pratt。 假定从字符串S中查找M，S的长度ls，M的长度lm，且（ls lm）。 朴素的字符串查找方法 从字符串S的第一个字符开始与M进行比较，如果匹配失
|
KMP算法是经典的字符串匹配算法，解决从字符串S，查找模式字符串M的问题。算法名称来源于发明者Knuth，Morris，Pratt。 朴素的字符串查找方法 KMP的字符串查找方法
此时匹配失败在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。 实例 #朴素匹配 def naive_match(s,p): m = len(s); n = len(p) for i in range(m-n+1):#起始指针i if s[i:i+n] == p: return True return False 关于kmp算法,讲的最好的当属阮一峰的<字符串匹配的KMP算法>.一路读下来,豁然开朗.
#KMP
def kmp_match(s,p):
m = len(s); n = len(p)
cur = 0#起始指针cur
table = partial_table(p)
while cur<=m-n:
for i in range(n):
if s[i+cur]!=p[i]:
cur += max(i - table[i-1],1)#有了部分匹配表,我们不只是单纯的1位1位往右移,可以一次移动多位
break
else:
return True
return False
#部分匹配表
def partial_table(p):
'''''partial_table("ABCDABD") -> [0,1,2,0]'''
prefix = set()
postfix = set()
ret = [0]
for i in range(1,len(p)):
prefix.add(p[:i])
postfix = {p[j:i+1] for j in range(1,i+1)}
ret.append(len((prefix&postfix or {''}).pop()))
return ret
print naive_match("BBC ABCDAB ABCDABCDABDE","ABCDABD")
print partial_table("ABCDABD")
print kmp_match("BBC ABCDAB ABCDABCDABDE","ABCDABD")
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |