KMP算法中next数组的构建与优化

1. 问题描述

KMP（Knuth-Morris-Pratt）算法用于解决字符串匹配问题，其核心是避免在匹配失败时完全回溯主串指针，而是利用已匹配部分的信息跳过不必要的比较。这个“已匹配部分的信息”存储在 next数组（也称为部分匹配表）中。
题目要求：

1. 解释 next数组 的定义与作用。
2. 详细推导 next数组的构建过程（包括未优化版本和优化版本）。
3. 给出代码实现与时间复杂度分析。

2. next数组的定义

给定模式串 pattern，长度为 m，next[i] 表示 模式串中前缀 pattern[0..i] 的最长公共真前后缀的长度。

• 真前后缀：前缀/后缀不能等于整个字符串本身。
• 例如 "abab"，前缀有 "a"、"ab"、"aba"，后缀有 "b"、"ab"、"bab"，公共真前后缀是 "ab"，长度为 2，所以 next[3] = 2。

作用：当模式串在位置 i 匹配失败时，将模式串右移，使 pattern[0..next[i-1]] 对齐到刚才已匹配的部分，主串指针不动。

3. 未优化的 next 数组构建步骤

以模式串 pattern = "ababc" 为例，m=5，下标从 0 开始。

3.1 约定

• next[0] = 0，因为单个字符没有真前后缀。
• 定义 len 表示当前已匹配的前后缀长度，初始 len = 0。
• 用指针 i 从 1 到 m-1 遍历模式串。

3.2 推导过程

1. i=1, pattern[1]='b'

   • len=0，pattern[len]='a'，pattern[i]='b'，不相等。
   • 回退：len>0 时可回退，但 len=0，所以 next[1]=0。
     （此时 len=0 不变）

2. i=2, pattern[2]='a'

   • len=0，pattern[0]='a'，pattern[2]='a'，相等。
   • len++ 变为 1，next[2]=len=1。

3. i=3, pattern[3]='b'

   • len=1，pattern[1]='b'，pattern[3]='b'，相等。
   • len++ 变为 2，next[3]=2。

4. i=4, pattern[4]='c'

   • len=2，pattern[2]='a'，pattern[4]='c'，不相等。
   • 回退：len>0，令 len=next[len-1]=next[1]=0，比较 pattern[0]='a' 与 'c' 仍不等，但 len=0 停止回退。
   • 此时 len=0，next[4]=0。

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

4. 未优化版本的代码

def build_next(pattern):
    m = len(pattern)
    next_arr = [0] * m
    length = 0  # 最长公共前后缀长度
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            next_arr[i] = length
            i += 1
        else:
            if length != 0:
                length = next_arr[length - 1]  # 关键回退
            else:
                next_arr[i] = 0
                i += 1
    return next_arr

5. 为什么需要优化 next 数组？

考虑模式串 pattern = "aaaaa"：

• 未优化 next: [0, 1, 2, 3, 4]
  匹配失败时，比如在 i=4 失败，会回退到 next[3]=3，但此时 pattern[3] 仍然等于刚才匹配的字符，会再次失败，多了一次不必要的比较。

优化思想：当 pattern[i] 与主串不匹配时，如果回退后 pattern[next[i-1]] 仍然等于 pattern[i-1]，那么这次匹配必然失败，可以直接跳过，继续回退。
优化后，next 数组变为 next 优化版本（有时称为 nextVal）。

6. 优化版的 next 数组构建

在构建 next 时，如果 pattern[i] == pattern[len]，则在回退时可以直接跳到更前面的位置。

6.1 调整构建逻辑

以 "ababc" 为例，我们沿用未优化的步骤，但在赋值 next[i] 时做判断：

1. 初始 next[0]=0，i=1, len=0。
2. i=1, pattern[1]='b' ≠ pattern[0]='a'，len=0，next[1]=0。
3. i=2, pattern[2]='a' = pattern[0]='a'，len=1，检查 pattern[2] 是否等于 pattern[1]？不相等，所以 next[2]=1。
4. i=3, pattern[3]='b' = pattern[1]='b'，len=2，检查 pattern[3] 是否等于 pattern[2]？不等，next[3]=2。
5. i=4, pattern[4]='c' ≠ pattern[2]='a'，len=0，next[4]=0。

这里没有重复字符，优化不明显。

再看 "aaaaa"：

• 未优化: [0,1,2,3,4]
• 优化过程：
  i=1, pattern[1]=pattern[0]，但回退时应该直接到 0，所以 next[1]=0。
  i=2, pattern[2]=pattern[1] 且 next[1]=0，所以 next[2]=0。
  以此类推，优化后 next=[0,0,0,0,0]。

6.2 优化版代码

def build_next_optimized(pattern):
    m = len(pattern)
    next_arr = [0] * m
    length = 0
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            # 优化：如果回退后的字符仍然相等，则继续回退
            if i + 1 < m and pattern[i + 1] == pattern[length]:
                next_arr[i] = next_arr[length - 1] if length > 0 else 0
            else:
                next_arr[i] = length
            i += 1
        else:
            if length != 0:
                length = next_arr[length - 1]
            else:
                next_arr[i] = 0
                i += 1
    return next_arr

更常见的写法是先构建未优化的next，再优化：

def build_next_val(pattern):
    next_arr = build_next(pattern)  # 未优化版本
    next_val = [0] * len(pattern)
    next_val[0] = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[next_arr[i]]:
            next_val[i] = next_val[next_arr[i]]
        else:
            next_val[i] = next_arr[i]
    return next_val

7. 时间复杂度分析

构建 next 数组时，i 从 1 到 m-1，每次 i 增加或 len 减少，len 减少次数有限，总体是 O(m) 时间。
优化版也是 O(m)。
匹配主串时 O(n)，整体 O(n+m)。

8. 总结要点

• next 数组 是 KMP 算法的核心，存储每个位置的最长公共真前后缀长度。
• 构建过程用双指针（i 与 len）和回退机制。
• 优化版（nextVal）避免连续相同字符导致的多余匹配失败。
• 代码实现简短，但需理解回退逻辑：len = next[len-1]。