微客导航 » 文章资讯 » Python实现字符串匹配的KMP算法

Python实现字符串匹配的KMP算法

2023-08-25 01:19:06 472

kmp算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。

#!/usr/bin/python
#coding=utf-8
"""
基于这篇文章的python实现
http://blog.sae.sina.com.cn/archives/307
"""
importunittest
defpmt(s):
"""
PartialMatchTable
"""
prefix=[s[:i+1]foriinrange(len(s)-1)]
postfix=[s[i+1:]foriinrange(len(s)-1)]
intersection=list(set(prefix)&set(postfix))
ifintersection:
returnlen(intersection[0])
return0
defkmp(big,small):
i=0
whilei
总结
以上所述是小编给大家介绍的Python实现字符串匹配的KMP算法，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对毛票票网站的支持！

返回顶部
3162201930
czq8825@qq.com

Python实现字符串匹配的KMP算法

热门推荐

随机推荐