KMP 字符串匹配算法原理与 next 数组推导

解析说明

• 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 实现了主串只遍历一次。

手动推导 next 数组

手动推导 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 方式模拟构建。

# 验证代码
def compute_next(pattern):
    m = len(pattern)
    next_arr = [-1] * m
    j = -1
    for i in range(1, m):
        while j != -1 and 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] ✔️