Python实现字符串匹配的KMP算法
作者:Goodspeed 时间:2021-02-10 05:03:45
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
"""
import unittest
def pmt(s):
"""
PartialMatchTable
"""
prefix = [s[:i+1] for i in range(len(s)-1)]
postfix = [s[i+1:] for i in range(len(s)-1)]
intersection = list(set(prefix) & set(postfix))
if intersection:
return len(intersection[0])
return 0
def kmp(big,small):
i = 0
while i < len(big) - len(small) + 1:
match = True
for j in range(len(small)):
if big[i+j] != small[j]:
match = False
break
if match:
return True
#移动位数 = 已匹配的字符数 – 对应的部分匹配值
if j:
i += j - pmt(small[:j])
else:
i += 1
return False
class kmpTests(unittest.TestCase):
def test_pmt(self):
self.assertEqual(pmt("A"),0)
self.assertEqual(pmt("AB"),0)
self.assertEqual(pmt("ABC"),0)
self.assertEqual(pmt("ABCD"),0)
self.assertEqual(pmt("ABCDA"),1)
self.assertEqual(pmt("ABCDAB"),2)
self.assertEqual(pmt("ABCDABD"),0)
self.assertEqual(pmt("AAAAAA"),5)
def test_kmp(self):
self.assertTrue(kmp("ABCD","CD"))
self.assertFalse(kmp("ABCD","BD"))
self.assertTrue(kmp("BBC ABCDAB ABCDABCDABDE","ABCDABD"))
if __name__ == '__main__':
unittest.main()
总结
以上所述是小编给大家介绍的Python实现字符串匹配的KMP算法网站的支持!
来源:https://www.cnblogs.com/goodspeed/p/3295456.html
标签:python,字符串,kmp
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
JavaScript 组件之旅(一):分析和设计
2009-09-21 10:52:00
![](https://img.aspxhome.com/file/UploadPic/20099/21/300px-data_queue-40s.png)
Python图像阈值化处理及算法比对实例解析
2022-08-14 19:32:33
![](https://img.aspxhome.com/file/2023/5/105805_0s.png)
python获取本地计算机名字的方法
2022-01-26 10:04:32
一个无组件上传的ASP代码
2007-10-09 19:49:00
python实现在多维数组中挑选符合条件的全部元素
2022-06-02 03:43:12
![](https://img.aspxhome.com/file/2023/7/102827_0s.jpg)
Django学习之静态文件与模板详解
2022-12-13 13:19:58
![](https://img.aspxhome.com/file/2023/5/107875_0s.png)
python简单贪吃蛇开发
2021-04-24 18:47:56
javascript实现锁定网页、密码解锁效果(类似系统屏幕保护效果)
2023-08-18 20:01:36
Python中处理字符串之islower()方法的使用简介
2021-03-26 16:40:35
Python魔术方法详解
2022-04-25 00:13:05
![](https://img.aspxhome.com/file/2023/8/94048_0s.png)
MSSQL存储过程分页,ASP存储过程分页
2009-09-11 12:50:00
opencv转换颜色空间更改图片背景
2023-12-20 19:01:29
python中的多重继承实例讲解
2022-06-18 01:51:05
![](https://img.aspxhome.com/file/2023/8/95568_0s.jpg)
利用Python自制网页并实现一键自动生成探索性数据分析报告
2023-01-19 13:20:12
![](https://img.aspxhome.com/file/2023/2/99172_0s.gif)
win10下安装Anaconda的教程(python环境+jupyter_notebook)
2023-11-27 13:27:08
![](https://img.aspxhome.com/file/2023/2/85232_0s.jpg)
利用python+ffmpeg合并B站视频及格式转换的实例代码
2021-06-09 21:14:00
Python通过psd-tools解析PSD文件
2023-05-25 12:08:47
form表单的submit方法和submit事件
2008-10-15 11:22:00
python实现根据主机名字获得所有ip地址的方法
2021-03-13 14:19:25
基于tensorflow for循环 while循环案例
2022-01-26 14:40:34