KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，其核心思想是**避免主串指针回溯**，通过预处理模式串构造 `next` 数组

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，其核心思想是避免主串指针回溯，通过预处理模式串构造 next 数组，使得在发生字符不匹配时，能够快速调整模式串的匹配位置。以下是针对你提供内容的完整解析与代码实现：

defcompute_next(pattern):"""计算模式串的 next 数组""" m =len(pattern) next_arr =[-1]* m # 初始化 next 数组，第一个元素为 -1 j =-1# 指向前缀末尾（初始为 -1）for i inrange(1, m):# i 指向后缀末尾while j !=-1and pattern[i]!= pattern[j +1]: j = next_arr[j]if pattern[i]== pattern[j +1]: j +=1 next_arr[i]= j return next_arr defkmp_search(text, pattern):"""KMP 算法主函数：返回模式串在主串中首次出现的起始下标，未找到返回 -1"""ifnot pattern:return0 n, m =len(text),len(pattern) next_arr = compute_next(pattern) j =-1# 模式串匹配指针（当前已匹配到的位置）for i inrange(n):# 遍历主串while j !=-1and text[i]!= pattern[j +1]: j = next_arr[j]# 失配时利用 next 跳转if text[i]== pattern[j +1]: j +=1if j == m -1:# 完全匹配return i - m +1# 返回起始位置return-1# 匹配失败# 示例使用 text ="abacbababbcbc" pattern ="abababb" next_table = compute_next(pattern)print("Next数组:", next_table)# 输出: [-1, 0, 0, 1, 2, 3, 4] pos = kmp_search(text, pattern)print(f"模式串 '{pattern}' 在主串中的起始位置: {pos}")

解析说明：

• next 数组含义：next[j] 表示模式串前 j+1 个字符中最长相等前后缀的长度减一（即回退位置）。例如 "abababb" 的 next = [-1,0,0,1,2,3,4]。
• 匹配过程：当 text[i] != pattern[j] 时，令 j = next[j]，无需移动 i，从而保证时间复杂度为 O(n+m)。
• 效率优势：相比朴素算法每次失配都需回溯主串指针，KMP 实现了主串只遍历一次。
  手动推导 KMP 算法中模式串的 next 数组，核心是对每个位置 j，求其子串 pattern[0…j] 的最长相等真前缀与真后缀的长度，并将该长度减一作为 next[j]（即回退到的位置下标）。我们以模式串 "abaabc" 为例，逐步推导其 next 数组。

✅ 模式串："abaabc"

我们将逐位计算 next[j]：

🔹 j = 0

• 子串："a"
• 无真前缀和真后缀 → 最长相等前后缀长度为 0
• next[0] = -1 （规定第一个值为 -1）

✅ next[0] = -1

🔹 j = 1

• 子串："ab"
• 前缀集合：{“a”}
• 后缀集合：{“b”}
• 相等前后缀：空 → 长度为 0
• next[1] = 0

✅ next[1] = 0

🔹 j = 2

• 子串："aba"
• 前缀：{“a”, “ab”}
• 后缀：{“a”, “ba”}
• 共同部分：“a” → 长度为 1
• 所以最长相等前后缀长度为 1 → 下标为 0
• next[2] = 0（因为要记录的是前缀最后一个字符的下标）

✅ next[2] = 0

🔹 j = 3

• 子串："abaa"
• 前缀：{“a”, “ab”, “aba”}
• 后缀：{“a”, “aa”, “baa”}
• 共同部分：“a” → 长度为 1 → 对应下标 0
• next[3] = 0

✅ next[3] = 0

🔹 j = 4

• 子串："abaab"
• 前缀：{“a”, “ab”, “aba”, “abaa”}
• 后缀：{“b”, “ab”, “aab”, “baab”}
• 共同部分：“ab” → 长度为 2 → 对应下标 1
• next[4] = 1

✅ next[4] = 1

🔹 j = 5

• 子串："abaabc"
• 前缀：{“a”, “ab”, “aba”, “abaa”, “abaab”}
• 后缀：{“c”, “bc”, “abc”, “aabc”, “baabc”}
• 没有公共非空相等前后缀？检查：
  • “a” vs “c” → 不等
  • “ab” vs “bc” → 不等
  • …
  • 仅可能匹配长度为 0
• 实际上唯一可能的是长度为 0
• next[5] = 0

✅ next[5] = 0

📊 最终结果：

✅ 总结推导方法（手动步骤）：

1. next[0] = -1 固定。
2. 对于每个后续位置 j ≥ 1：
   • 考察子串 pattern[0..j]
   • 找出它的所有真前缀和真后缀
   • 找出其中最长的相等前后缀
   • 记录这个最长前缀的最后一个字符的下标 → 即为 next[j]
3. 可用递推思想辅助：若已知前面的 next 值，可通过类 KMP 方式模拟构建。

# 验证代码defcompute_next(pattern): m =len(pattern) next_arr =[-1]* m j =-1for i inrange(1, m):while j !=-1and pattern[i]!= pattern[j +1]: j = next_arr[j]if pattern[i]== pattern[j +1]: j +=1 next_arr[i]= j return next_arr print(compute_next("abaabc"))# 输出: [-1, 0, 0, 0, 1, 0] ✔️