最浅显易懂的 KMP 算法讲解-奇乐编程学院-bilibili
KMP的next数组中保存了: 主串中最长的已匹配的字符。线性时间复杂度：主串指针不回退，子串指针回退到已经匹配的部分的后面（跳过已匹配的部分)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
def kmp_search(string, patt): # string主串，patt子串
next = build_next(patt):
i = 0 # 主串中的指针
j = 0 # 子串中的指针
while i < len(string):
if string[i] == patt[j]: # 字符匹配，指针后移
i += 1
j += 1
elif j > 0: # 字符失配，根据 next 数组跳过子串前面的一些字符
j = next[j - 1]
else: # 子串第一个字符就失配
i += 1
if j == len(patt): # 匹配成功
return i - j
|
next 数组统计了各字符（包括它在内）之前已重复部分的长度。构造时有两个指针，前方指针指向前缀长度的后面一个字（前缀长度就是该指针之前的(不包括指向的)字符个数）；后方的指针指向当前字符（后缀）。后方指针一直后移，而前方指针要回退查看后缀是否存在与前缀中。
若两指针指向的字符相同，则后方指针对应的next数组元素为: 前缀长度数值+1，然后两个指针都后移一位；
如果它们指向的字符不相同，就看看后缀是否是前缀的一个子集（前缀中是否包含以后缀为结尾的短串，所以就要回到它前面的另一次重复看是否与后缀相接），则后方指针不动，前方指针回退到它左侧字符第一次出现时的下一个字符上（也就是左侧字符对应的前缀长度的下一个字符上，也就是跳过比较左侧字符对应的前缀长度个字符），因为再往前就是与此左侧字符的前缀重复的部分，比较这两个指针指向的字符，相同的话，也就是能连上这个后缀，则后方指针指向的next数组元素就是前方指针的前缀长度+1，然后两指针前移；不同的话，前方指针再回退，再与后缀比较，移动到第一个字符(前缀长度=0)还是与后缀不同的话就置0，后方指针前移，前方指针停在第一字符上。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
def build_next(patt):
"""
构造next数组
"""
next = [0] # next数组 初值元素一个0
prefix_len = 0 # 当前前缀长度
i = 1 # 后方指针
while i < len(patt): # 一次遍历
if patt[prefix_len] == patt[i]: # 前方指针字符 = 后方指针指向字符
prefix_len += 1 # 前缀长度+1
next.append(prefix_len)
i += 1 # 后方指针后移
else:
if prefix_len == 0: # 前方指针回到了第一个字符
next.append(0) # next[i]=0
i += 1
else:
prefix_len = next[prefix_len - 1] # 前方指针回退到左侧字符的前缀长度的下一个字上，也就是前缀长度变成左侧字符的前缀长度
return next
|