kmp算法

kmp算法

代码

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# -*- coding:utf-8 -*-
"""
author: fantasy
time: 2021/09/16
desc: s中是否包含p,如果包含,返回索引,否则-1
"""
"""
1,求最长前后缀
i 指向最长后缀的末尾
j 指向最长前缀的末尾
s[i] == s[j] j++ next[i] = j
s[i] != s[j] 回退

2,kmp查找时
如果在模式串j处失配,则j跳转到next[j-1]处
如果成功匹配,i, j各进一步
"""


def getnext(s):
"""
next[i]表示是s[0~i]的最长公共前后缀
i 指向最长后缀的末尾
j 指向最长前缀的末尾
i
abcab
j
"""
n = len(s)
# 初始化 next[0] = 0 一个字母没有前缀、后缀
next = [0 for _ in range(n)]
j = 1
for i in range(n):
if s[i] == s[j]:
j += 1
else:
while j > 0 and s[i] != s[j]:
# j指针回退
j = next[j-1]
next[i] = j
print(next)
return next


def kmp(t, p):
next = getnext(p)
n, m = len(t), len(p)
i = j = 0
while i < n:
if t[i] != p[j]:
if j == 0:
# 模式串第一位就不匹配
i += 1
else:
# 模式串某一位不匹配,根据next数组移动模式串,注意next[i]的定义
j = next[j - 1]
else:
# 主串与模式串继续往前匹配
i += 1
j += 1
if j == m - 1:
# 匹配到了最后一位,i-(m-1)得到起始位置
return i - (m - 1)


if __name__ == '__main__':
p = "helhel"
t = "hello helhel world"
r = kmp(t, p)
print(r)