实现KMP字符串匹配算法中next数组的构建与优化

题目描述
KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，其核心在于当匹配失败时，主串指针不回溯，而是利用模式串的next数组（也称部分匹配表）将模式串移动到下一个可能匹配的位置。next数组的构建是KMP算法的关键，它表示模式串中每个前缀的最长相同真前缀和真后缀的长度。理解并手写next数组的构建是常见的面试考点，需要清晰掌握其递推逻辑和优化细节。

解题过程循序渐进讲解

步骤1：理解next数组的定义

• 对于模式串P（长度为m），next数组是一个长度为m的数组，next[i]表示子串P[0...i]（即从开头到位置i的前缀）的“最长相同真前缀和真后缀的长度”（即最长公共前后缀长度）。
• 注意是“真”前缀/后缀，即不包括自身。例如，前缀"abab"的最长相同真前缀和真后缀是"ab"，长度为2。
• 示例：模式串P = "ababc"
  • i=0：子串"a"，没有真前缀/后缀，next[0] = 0（通常定义为-1或0，后续说明）。
  • i=1：子串"ab"，真前缀"a"，真后缀"b"，无相同，next[1] = 0。
  • i=2：子串"aba"，最长相同真前缀/后缀是"a"，长度1，next[2] = 1。
  • i=3：子串"abab"，最长相同是"ab"，长度2，next[3] = 2。
  • i=4：子串"ababc"，无相同，next[4] = 0。

步骤2：构建next数组的基本思想（递推法）

• 暴力求解每个前缀的最长公共前后缀效率低（O(m²)），KMP使用动态规划思想在O(m)时间构建。
• 核心递推：假设已知next[0...i-1]，求next[i]。定义指针j表示当前已匹配的前缀长度。
• 初始化：next[0] = -1（方便编程，表示退无可退）；j = -1；i = 1（从第二个字符开始）。
• 递推过程（i从1到m-1）：
  1. 如果j == -1或P[i-1] == P[j]，则j++，next[i] = j，i++。
  2. 否则，令j = next[j]（回退到前一个匹配位置）。
• 原理：j实际上指向当前已匹配的前缀末尾，通过回退j来尝试缩短前缀，直到找到匹配或退到开头。

步骤3：逐步演示例题
以模式串P = "ababc"为例，构建next数组（采用next[0] = -1的定义）。

1. 初始化：next[0] = -1，i=1，j=-1。
2. i=1：j=-1，执行j++ => j=0，next[1] = 0，i++ => i=2。
3. i=2：比较P[1]='b'和P[0]='a'，不相等，且j=0不为-1，回退j = next[0] = -1。
   • 回退后j=-1，执行j++ => j=0，next[2] = 0，i++ => i=3。
4. i=3：比较P[2]='a'和P[0]='a'，相等，执行j++ => j=1，next[3] = 1，i++ => i=4。
5. i=4：比较P[3]='b'和P[1]='b'，相等，执行j++ => j=2，next[4] = 2，i++结束。
   最终next = [-1, 0, 0, 1, 2]。
   注意：这个结果与步骤1定义（长度值）不同，因为next[0]设为-1，但本质一致（实际匹配时j+1就是长度）。面试中需确认定义，常见是next[0] = -1。

步骤4：next数组的优化（nextVal数组）

• 问题：当P[i]与主串字符不匹配时，根据next[i]回退到位置j，但如果P[i] == P[j]，那么回退后字符依然相同，会再次不匹配，导致多余比较。
• 优化：在构建next数组时，如果P[i] == P[next[i]]，则next[i]应直接赋值为next[next[i]]，直到字符不同。
• 示例：P = "ababc"，原始next = [-1, 0, 0, 1, 2]
  • i=1：P[1]='b'，next[1]=0，P[0]='a'，不同，无需优化。
  • i=4：P[4]='c'，next[4]=2，P[2]='a'，不同，无需优化。
    但若P = "aaaaa"，原始next = [-1, 0, 1, 2, 3]，优化后nextVal = [-1, -1, -1, -1, -1]，避免多次回退。
• 优化后的构建：在步骤2的j++后，如果P[i] == P[j]，则next[i] = next[j]，否则next[i] = j。

步骤5：代码实现与验证

def build_next(pattern: str):
    m = len(pattern)
    next_arr = [0] * m
    next_arr[0] = -1
    i, j = 1, -1
    while i < m:
        if j == -1 or pattern[i-1] == pattern[j]:
            j += 1
            # 优化：如果字符相同，直接取next[j]
            if pattern[i] == pattern[j]:
                next_arr[i] = next_arr[j]
            else:
                next_arr[i] = j
            i += 1
        else:
            j = next_arr[j]
    return next_arr

# 测试
P = "ababc"
print(build_next(P))  # 输出: [-1, 0, 0, 1, 0]（优化后，注意i=4的next[4]从2变为0）

验证：对于P = "ababc"，优化后next = [-1, 0, 0, 1, 0]，当i=4不匹配时直接回退到0，跳过中间冗余比较。

总结
KMP的next数组构建是动态规划思想的经典应用，通过前缀的自匹配高效推导。务必理解j回退的涵义，并注意优化细节。在面试中，可以先写出基础版本，再讨论优化，展现全面性。