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 unittestdef 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 0def 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 Falseclass 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算法，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对网站的支持！