Python实现字符串匹配的KMP算法
程序员文章站
2023-11-16 16:34:46
kmp算法
kmp算法是一种改进的字符串匹配算法,由d.e.knuth,j.h.morris和v.r.pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简...
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算法,希望对大家有所帮助