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

147 浏览量更新于2023-05-04 评论收藏 47KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

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

"""

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算法，希望对大家有所帮助，如果大家有任何疑问请给我留言，

小编会及时回复大家的。在此也非常感谢大家对软件开发网网站的支持！

您可能感兴趣的文章您可能感兴趣的文章:详解Python的数据库操作（pymysql）python dlib人脸识别代码实例python爬虫简单的添加代理进行访问

的实现代码详解python项目实战:模拟登陆CSDNPython GUI编程完整示例python实现kmp算法的实例代码详解python多线程

之间的同步(一)Python将列表数据写入文件（txt, csv，excel）详解python读取imagePython选择网卡发包及接收数据包

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余0页未读，立即下载

weixin_38663151

粉丝: 3
资源: 897

会员权益专享

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

评论0

会员权益专享

最新资源

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

评论0

详解KMP算法以及python如何实现

KMP算法（python）

python实现kmp算法的实例代码

python 149字符串匹配KMP算法

实现字符串匹配KMP算法

字符串匹配kmp算法

串匹配问题kmp算法

字符串匹配算法KMP

kmp算法实现字符串匹配的完整代码

python字符串匹配💍

python 模糊匹配KMP 算法 案例

正确运用顺序串的某些基本操作实现 KMP 算法，并理解 KMP 算法 python实现

kmp算法匹配字符串

python实现kmp算法

字符串的模式匹配（BF算法，KMP算法）代码实现

用python编写字符串匹配问题 给定一个s字符串和一个n字符串，在s字符串中找出n字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1（需要给出多个测试用例，证明算法的正确性）

1、字符串匹配问题 给定一个s字符串和一个n字符串，在s字符串中找出n字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1 kmp算法 代码+算法分析

kmp算法python实现

算法字符串匹配问题

会员权益专享

最新资源

python 模糊匹配KMP 算法案例

用python编写字符串匹配问题给定一个s字符串和一个n字符串，在s字符串中找出n字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1（需要给出多个测试用例，证明算法的正确性）

1、字符串匹配问题给定一个s字符串和一个n字符串，在s字符串中找出n字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1 kmp算法代码+算法分析