kmp算法
kmp算法是一种改进的字符串匹配算法，由d.e.knuth，j.h.morris和v.r.pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称kmp算法）。kmp算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#! /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