KMP算法（Knuth-Morris-Pratt）的next数组计算优化 描述 KMP算法是一种高效的字符串匹配算法，其核心在于通过预处理模式串（Pattern）生成一个next数组（或称部分匹配表），用于在匹配失败时跳过不必要的比较。next数组的优化计算是KMP算法的关键步骤，旨在避免重复回溯，将时间复杂度降至O(n+m)。 解题过程 next数组的基本定义 next[ i]表示模式串P的前缀子串P[ 0:i ]（长度为i+1）中，最长的相等真前缀与真后缀的长度（不包括子串本身）。例如，模式串"ABABC"的next数组计算如下： i=0: 子串"A" → 无真前缀/后缀，next[ 0 ] = -1（特殊标记） 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" → 真前缀"ABA"与真后缀"ABC"不相等，退而求"AB"与"BC"不相等，最后"A"与"C"不相等，next[ 4 ] = 0 未优化的next计算（朴素方法） 直接对每个位置i，枚举所有可能的前后缀长度k（从大到小），比较P[ 0:k-1]和P[ i-k+1:i ]。此方法效率低，时间复杂度为O(m²)，未利用已计算的结果。 优化思路：递推计算 核心思想是利用已计算的next[ 0]到next[ i-1]来推导next[ i]，避免重复比较。设当前需要计算next[ i]，并已知next[ i-1] = j，即P[ 0:j-1] = P[ i-j:i-1 ]： 若P[ j] == P[ i]，则直接扩展相等前后缀，next[ i ] = j + 1 若P[ j] ≠ P[ i]，则需缩短匹配长度，令j = next[ j]，回退到更短的前缀位置继续比较，直到j = -1（无法回退）时 next[ i ] = 0 优化计算步骤详解 以模式串P = "ABABC"为例： 初始化：next[ 0 ] = -1, i = 1, j = -1 i=1: j = -1 → 无法回退，比较P[ 0]和P[ 1]（'A'≠'B'）→ next[ 1 ] = 0, j=0 i=2: j=0, 比较P[ 0]和P[ 2]（'A'='A'）→ next[ 2 ] = j+1 = 1, j=1 i=3: j=1, 比较P[ 1]和P[ 3]（'B'='B'）→ next[ 3 ] = 2, j=2 i=4: j=2, 比较P[ 2]和P[ 4]（'A'≠'C'）→ j回退为next[ 2 ]=1 继续比较P[ 1]和P[ 4]（'B'≠'C'）→ j回退为next[ 1 ]=0 比较P[ 0]和P[ 4]（'A'≠'C'）→ j回退为next[ 0]=-1 → next[ 4 ]=0 算法正确性分析 递推过程保证了每次比较都是基于已知的最长相等前后缀，通过j的回退（next[ j ]）逐步尝试更短的匹配，避免了重复扫描。此方法将next数组计算优化至O(m)。 关键点 优化后的next计算利用历史信息，通过动态规划思想避免冗余操作 j的回退机制（j = next[ j ]）是优化的核心，类似"前缀的前缀"的跳跃匹配 实际代码中需注意边界条件（如j=-1时的处理）