Python实现字符串匹配的KMP算法
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算法,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对毛票票网站的支持!
热门推荐
1 训练狗狗搜寻
2 如何训练狗狗装死
3 狗狗训练书
6 怎么训练狗狗拜年
8 狗狗训练游戏
10 狗狗嗅觉训练
11 怎么训练狗狗在笼子里不叫
12 怎么训练狗狗站立走路
13 怎么训练狗狗在马桶上
14 狗狗尿尿怎么训练
15 训练狗狗用品
16 泰迪狗狗的训练方法大小便
17 训练狗狗可以打吗
18 王曼丽的狗狗训练