KMP
思路
KMP（Knuth-Morris-Pratt）算法是一种在文本串中查找子串出现位置的算法。它的基本思想是利用匹配失败后的信息，尽量减少模式串与文本串的匹配次数以达到快速匹配的目的。
假设现在有文本串S和模式串P，我们要在S中查找P的出现位置。在暴力算法中，我们每次都从S的第一个字符开始匹配，如果不匹配就从S的第二个字符开始匹配，以此类推。而KMP算法则不同，它会利用匹配失败后的信息，跳过一些不必要的匹配过程，从而减少匹配的次数。
为了实现这一目的，KMP算法需要预先计算出一个“部分匹配”的数组，即next数组。next数组的含义是，当匹配失败时，模式串应该跳过的字符数。具体来说，假设现在文本串匹配到 i 位置，模式串匹配到 j 位置，匹配失败，则模式串应该跳过 next[j] 个字符，然后继续匹配。在文本串S和模式串P匹配时，我们也是按照暴力匹配的方式来匹配的，但是当匹配失败时，我们会利用next数组跳过一些字符，使得模式串向前移动的位数尽可能的少，最好是不移到第一位就可以继续匹配了。
KMP算法的时间复杂度是O(n+m)，其中n是文本串的长度，m是模式串的长度。这比暴力算法的时间复杂度O(nm)要快得多。
代码的核心原理：
i逐个遍历目标串，j指向模式串
- j匹配不成功跳next
- j匹配成功直接后移
内部while循环演示（跳next的过程）：
next数组（记录最长相同真子前后缀）：
注意
代码
def get_next(pattern):
# 获取模式串的长度
n = len(pattern)
# 初始化next数组
next = [-1] * n
# j表示当前正在计算的位置
j = 0
# k表示前缀中最长的相同前后缀的长度
k = -1
while j < n - 1:
# 如果k为-1，或者pattern[j] == pattern[k]，则next[j+1] = k+1
if k == -1 or pattern[j] == pattern[k]:
j += 1
k += 1
next[j] = k
# 如果pattern[j] != pattern[k]，则让k指向next[k]
else:
k = next[k]
# 返回next数组
return next
def kmp_search(text, pattern):
# 获取文本串和模式串的长度
m = len(text)
n = len(pattern)
# 计算next数组
next = get_next(pattern)
# j表示当前正在匹配的位置
j = 0
# 遍历文本串
for i in range(m):
# 如果文本串的字符text[i]和模式串的字符pattern[j]不匹配，则让j指向next[j]
while j > 0 and text[i] != pattern[j]:
j = next[j]
# 如果文本串的字符text[i]和模式串的字符pattern[j]匹配，则让j加1
if text[i] == pattern[j]:
j += 1
# 如果j等于n，则表示匹配成功
if j == n:
# 返回匹配的位置
return i - j + 1
# 如果匹配失败，返回-1
return -1
END
标签：数据结构,匹配,pattern,模式,next,text,文本 From： https://www.cnblogs.com/icbm/p/17005573.html