KMP算法（二)

本篇正是 KMP 的核心。我将严格结合“KMP算法（一）”前面提到的“部分匹配值（PM 表）”来讲，并且不写完整 KMP 代码，只讲：

• next 数组到底是什么

• 它和 PM（部分匹配值）的关系

• next 数组的严格定义

• next 数组是如何一步一步算出来的

• next 在匹配失败时究竟起什么作用

一、从“简单模式匹配”说起

在朴素模式匹配中：

• 主串指针 i

• 模式串指针 j

当发生失配时：

i 回退
j 回到 0

大量重复比较，时间复杂度 O(nm)

KMP 的核心目标

主串指针 i 永不回退，只移动模式串指针 j

那问题来了：

j 应该回退到哪里？

答案：next 数组

二、next 数组的本质

next[j] = 模式串中，
在第 j 位失配时，
模式串指针 j 应该跳转到的位置

注意：
❗不是随便跳
❗不是回到 0
❗是一个**“最合理、最大化利用已匹配信息的位置”**

三、next 数组 = 部分匹配值（PM）的工程化形式

你前面已经接触过这个概念：

部分匹配值（Partial Match，PM）=   子串的“最长相等前后缀长度”

举例

模式串

P = "ababa"

它的所有前缀子串

所以 PM 表是：

PM = [0, 0, 1, 2, 3]

那 next 数组和 PM 什么关系？

在 408 定义中：

next[j] = PM[j-1]

（j 从 1 开始编号）

转换成下标从 0 开始的 next 数组

next = [0, 0, 1, 2, 3]

注意：
这里的 next 不是跳过字符数，而是**“下一步 j 去哪里”**

四、next 数组到底“帮我们干了什么”

我们回到前面的那个经典失配场景：

主串 & 模式串

主串：ababcabcacbab
模式串：abcac

模式串 abcac 的 PM / next

我们先算 PM：

PM = [0, 0, 0, 1, 0]
next = [0, 0, 0, 1, 0]

第一趟匹配（重点）

主串： a b a b c
模式： a b c a c
↑ ↑

匹配到：

ab 匹配成功
c ≠ a 失配

已匹配字符数 = 2

最后一个匹配字符下标 = 1

next[1] = 0

KMP 的“核心公式”）

模式串右移位数 = 已匹配字符数 – 对应的部分匹配值

代入：

2 – 0 = 2

👉 模式串整体右移 2 位
👉 主串指针 不回退

为什么这是“最优”的？

因为：

• 已经知道 ab 匹配成功

• 而 ab 的最长相等前后缀长度为 0

• 所以模式串中没有任何前缀可以与已匹配后缀复用

• 只能整体跳过

五、next 数组的数学含义（非常重要）

对于模式串 P：

next[j] = k 表示：
在 P[0…j-1] 中
长度为 k 的前缀
等于长度为 k 的后缀

也就是说：

P[0 … k-1] == P[j-k … j-1]

所以失配时为什么能跳？

因为：

• P[0…k-1] 已经“等价于”刚刚匹配过的后缀

• 不用再重新比较

• 直接把 j 调到 k

这就是 KMP 能做到 O(n+m) 的根本原因。

六、next 数组是“如何求出来的”（思想版，不写代码）

求 next 的过程，本质上也是一个自匹配过程：

用 模式串自己匹配自己

核心变量含义（思想）

• j：当前计算 next 的位置

• k：当前最长相等前后缀长度

递推思想（非常重要）

当我们已经知道：

next[0…j-1]

要算 next[j]：

这一步其实就是：

“失配时，用 next 再跳一次”

next 的计算过程，本身就是 KMP 思想的体现。

七、一句话终极总结

next 数组记录了模式串在失配时应跳转的位置，
本质是模式串各前缀的最长相等前后缀长度，
它使得主串指针不回退，从而将匹配复杂度降为 O(n+m)。