KMP算法（Knuth-Morris-Pratt）的next数组计算优化

1. 问题背景

KMP算法用于高效解决单模式字符串匹配问题：给定一个文本串 T 和一个模式串 P，在 T 中快速找到 P 的出现位置。其核心思想是当匹配失败时，利用已匹配的信息跳过不必要的比较，避免回溯文本串指针。这一能力依赖于一个预处理数组——next数组（或称前缀函数），它记录了模式串的“自匹配”信息。

2. 基础next数组的定义与计算

2.1 next数组的含义

对于模式串 P[0..m-1]，next[i] 表示子串 P[0..i] 的最长公共真前缀和真后缀的长度（真前缀/真后缀指不包含整个字符串本身）。
例如：P = "ababc"

• i=0: "a" → 无公共真前缀/后缀，next[0] = 0
• i=1: "ab" → 无公共，next[1] = 0
• i=2: "aba" → 公共部分 "a"，长度=1
• i=3: "abab" → 公共部分 "ab"，长度=2
• i=4: "ababc" → 无公共，next[4] = 0

2.2 朴素计算方法的缺陷

直接对每个 i 枚举所有可能的前缀/后缀会达到 O(m²) 时间复杂度，无法发挥KMP的整体 O(n+m) 优势。

3. 优化思路：递推计算next数组

核心观察：next数组本身可以像KMP匹配过程一样递推计算，利用已计算的 next[0..i-1] 快速得到 next[i]。

3.1 递推过程详解

1. 初始化：

   • next[0] = 0（单个字符无公共部分）
   • 设置指针 i = 1（当前计算位置），j = 0（指向前缀的末尾）

2. 循环计算（i 从 1 到 m-1）：

   • 情况1：若 P[i] == P[j]，则公共长度可扩展：next[i] = j + 1，然后 i++, j++
   • 情况2：若 P[i] != P[j] 且 j > 0，则回溯 j = next[j-1]（利用已计算信息跳转）
   • 情况3：若 P[i] != P[j] 且 j == 0，则 next[i] = 0，i++

3.2 示例：P = "ababc"

结果：next = [0,0,1,2,0]

4. 进一步优化：避免连续失配

4.1 问题场景

考虑 P = "aaaab"，按上述方法得到 next = [0,1,2,3,0]。当匹配失败时（例如在 i=3 失配），会回溯到 next[3-1]=2，但 P[3] 和 P[2] 都是 'a'，必然继续失配，导致多次回溯。

4.2 优化方法

在递推计算 next[i] 时，若 P[i] == P[j]，则检查 P[i+1] 是否等于 P[j+1]：

• 如果相等，则直接令 next[i] = next[j]（跳过相同的字符比较）
• 否则正常赋值 next[i] = j + 1

优化后的代码逻辑：

def build_next_optimized(P):  
    m = len(P)  
    next_arr = [0] * m  
    j = 0  
    for i in range(1, m):  
        while j > 0 and P[i] != P[j]:  
            j = next_arr[j-1]  # 回溯  
        if P[i] == P[j]:  
            # 避免连续失配：若下一字符相同则直接继承  
            if i+1 < m and j+1 < m and P[i+1] == P[j+1]:  
                next_arr[i] = next_arr[j]  
            else:  
                next_arr[i] = j + 1  
            j += 1  
        else:  
            next_arr[i] = 0  
    return next_arr  

4.3 优化效果

对 P="aaaab"，优化后的 next = [0,0,0,0,0]：

• 当在 i=4 失配时直接跳回 0，避免中间回溯步骤。

5. 总结

• 基础next计算通过递推将时间复杂度降至 O(m)。
• 优化next计算通过避免连续失配进一步减少匹配时的回溯次数，提升实际性能。
• 该优化在模式串包含重复字符时效果显著，是工业级KMP实现的重要技巧。