KMP 算法+Python 实现

KMP 算法

字符串匹配有很多算法可以实现,Knuth-Morris-Pratt 算法(简称KMP)是最常用的之一,时间复杂度为 O(m+n),其中 m 为模式串的长度,n 为目标串的长度。
具体的 KMP 算法还是比较复杂的,推荐阅读参考的两篇文章。

Python 代码

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
class KMP(object):
"""KMP algorithm."""
def kmp(self, s, pattern):
"""KMP string matching function.

Args:
s: str, target string.
pattern: str, pattern string.

Returns:
index: int, the starting matching index of s (-1 if cannot match).
"""
__next = self.get_next(pattern)
i = j = 0 # 分别为 s 和 pattern 的指针
while i < len(s) and j < len(pattern):
if j == -1 or s[i] == pattern[j]:
# j 为 -1 是由 j = __next[j] 回溯产生的,即回溯到了 pattern 开头。
# 说明此处没有公共前缀与后缀,两个指针同时后移,相当于从 pattern 的头部开始重新匹配。
i += 1
j += 1
else:
j = __next[j]
if j == len(pattern):
return i - j
return -1

def get_next(self, pattern):
"""Get 'next' array for a pattern string."""
# 注:得到 next 数组的方法相当于 pattern 自身与自身的匹配算法
# 不同的是,因为 next[0] = -1,所以相当于 pattern 与 pattern[1:] 匹配
__next = [0] * len(pattern)
__next[0] = -1
i = 1 # pattern[1:] 的指针
j = 0 # pattern 的指针
while i < len(pattern) - 1: # pattern[1:] 长度只有 len(pattern) - 1
if j == -1 or pattern[i] == pattern[j]:
i += 1
j += 1
__next[i] = j
else:
j = __next[j]
return __next


if __name__ == "__main__":
s = "ababababca"
p = "abababca"
# print("Next:", KMP().get_next(p))
print(KMP().kmp(s, p))

参考

https://www.zhihu.com/question/21923021/answer/281346746
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

文章目录
  1. 1. KMP 算法
  2. 2. Python 代码
  3. 3. 参考
|

载入天数...载入时分秒...