02KMP算法
02KMP算法
1. 最长前缀后缀
2. 课本实现
课本上的 KMP 算法数组和字符串索引都是从 1 开始，我们设模式串为 ，匹配串为 。
我们用 表示当第 个字符匹配失败时，应该跳转到的位置，即其中 。
2.1 KMP 搜索
若 ，需要找 的位置，因此只需找 。若正好有则可以继续向前匹配。否则可能匹配的位置一定出现在前 之内，因此贪婪匹配 ，注意到有因此自然带来递推实现。
下面给出代码实现，为了与实际 str，list 作区分，这里写作 Str，Lst，其中索引 0 表示长度。
def kmp_search(text: Str, pattern: Str, next: Lst[int]):
n = text[0]
m = pattern[0]
j = 1
for i in range(1, n + 1):
while j > 0 and text[i] != pattern[j]:
j = next[j]
# 如果 text[i]==pattern[j], 此时 i, j 依次递增即可
# 如果 text[i]!=pattern[j], 此时 j=0, j+=1 正好从 1 从头开始
j += 1
if j > m:
return i - m + 1
return -1
2.2 next 数组
下面需要找到 ，即 。对于 ，如果有即此时显然有 ，因此
如果不匹配，类似于 KMP 搜索，可能匹配的位置出现在前 之内，即 ，而注意到因此依然是递推。
下面也给代码实现：
def get_next(pattern: Str) -> Lst[int]:
m = pattern[0]
next = Lst(m, 0) # next[1] = 0
k = 0
for i in range(2, m + 1):
while k > 0 and pattern[i - 1] != pattern[k]:
k = next[k]
k += 1
next[i] = k
return next
2.3 nextval 数组
按照前面的 KMP 搜索，如果 ，此时需要去找 。但是如果 ，也一定会有 ，此时需要额外的再去找 。因此不妨在建立 时就进行检测，直接令就可以省去构建过程。
def get_nextval(pattern: Str) -> Lst[int]:
m = pattern[0]
nextval = Lst(m, 0)
k = 0
for i in range(2, m + 1):
while length > 0 and pattern[i - 1] != pattern[k]:
k = nextval[k]
k += 1
if pattern[i] == pattern[k]:
nextval[i] = nextval[k]
else:
nextval[i] = k
return nextval
3. 实际实现
实际实现中，字符串索引从 0 开始。此时 需要修改为随之修改其余代码即可。
def kmp_search(text: str, pattern: str, next: list[int]):
n = len(text)
m = len(pattern)
j = 0
for i in range(n):
while j >= 0 and text[i] != pattern[j]:
j = next[j]
j += 1
if j == m:
return i - m + 1
return -1
def get_next(pattern) -> list[int]:
m = len(pattern)
next = [0] * m
next[0] = k = -1
for i in range(1, m):
while k >= 0 and pattern[i - 1] != pattern[k]:
k = next[k]
k += 1
next[i] = k
return next
def get_nextval(pattern) -> list[int]:
m = len(pattern)
nextval = [0] * m
nextval[0] = k = -1
for i in range(1, m):
k = nextval[i - 1]
while k >= 0 and pattern[i - 1] != pattern[k]:
k = nextval[k]
k += 1
if pattern[i] == pattern[k]:
nextval[i] = nextval[k]
else:
nextval[i] = k
return nextval