KMP 字符串匹配可视化

KMP，全称 Knuth-Morris-Pratt，是一个非常经典的字符串匹配算法。它要解决的问题很直接：在一个较长的文本串中，快速找到模式串出现的位置。

为什么 KMP 很重要

朴素字符串匹配在失配时，通常会把模式串右移一位，然后从头重新比较。这样会重复检查很多已经比较过的字符。

KMP 的关键优化在于：先为模式串构造一个辅助数组，也就是 LPS 数组。

• LPS[i] 表示 pattern[0..i] 这个前缀里，最长的“真前缀 = 真后缀”的长度
• 有了这个信息，失配时就不必把模式串指针退回到 0
• 相反，可以直接跳到下一个仍然有可能匹配的位置

这就是 KMP 比朴素匹配更高效的原因。

LPS、next 和 nextval 到底是什么关系

如果你看过不同教材、博客或者课程，很可能会发现 KMP 的辅助数组写法并不统一。

• LPS 这是现代代码实现里最常见的表达方式，强调的是“最长相等前后缀的长度”。
• 经典 next 这是较早教材里很常见的写法，强调的是“失配之后模式串指针应该跳到哪里”。
• nextval 它是在经典 next 基础上的进一步优化。核心目的是避免某些回退位置虽然合法，但回退后依然会立刻遇到同样的字符冲突，导致一次没有意义的重复比较。

所以它们不是三个互不相关的算法，而是 同一个 KMP 思想在不同教材背景和实现风格下的不同表达。

从教学历史上看，很多较早的教材会先介绍 next 数组。
这种写法非常直接，它不强调“最长相等前后缀的长度”，而是直接告诉你：

• 当前模式串在位置 j 失配时
• 下一步应该把模式串指针回退到哪里

因此你可以把经典 next 看成是一种“更早期、也更直接的 KMP 回退表表达方式”。

需要特别注意的是：不同资料里的 next 定义并不完全一致。
为了方便和现代 LPS 一起对照，本页面的理论区采用一种常见的经典约定：

• next[0] = -1

这样你在阅读页面时，就不会把不同教材里的数组定义混在一起。

为什么还会有 nextval

经典 next 已经能避免很多重复比较，但它在某些模式串结构下，仍然可能让回退后的下一次比较显得“有点浪费”。

典型场景是：

• 模式串里有连续或重复的字符结构
• 回退到 next[j] 之后
• 新位置对应的字符和刚刚失配位置准备比较的字符其实还是一样

这样虽然算法逻辑仍然正确，但下一次比较很可能马上再次失败，于是就多做了一次没有实际收益的字符比较。

nextval 的动机正是解决这个问题：

• 如果回退到某个旧位置后，模式串字符仍然会和当前字符形成同样的冲突
• 那就继续沿着回退链再跳一步
• 直接跳到一个更有希望产生新信息的位置

所以可以把 nextval 理解成：

• 它不是另一套全新的 KMP
• 而是对经典 next 的进一步优化
• 优化目标是减少某些“回退后仍然立刻冲突”的冗余比较

这也是为什么很多资料会说：

• next 是早期最经典的 KMP 回退表
• nextval 是在 next 基础上继续优化得到的版本

这个页面怎么看

页面分成两个互相关联的部分：

1. 前缀表构建 这里演示当前模式串的 lps 数组是怎么一步步算出来的。
2. KMP 匹配过程 这里演示文本指针 i 和模式串指针 j 在匹配过程中如何移动。

当发生失配时：

• 如果 j > 0，就让 j 回退到 lps[j - 1]
• 如果 j === 0，就只能继续向右移动文本指针

如果你之前接触的是 next 或 nextval 版本的讲法，可以把本页的主动画理解成：
同样的回退逻辑，只是这里用更接近现代实现的 LPS 表达方式展示出来。

换句话说：

• 页面顶部的动态交互区重点帮助你理解“匹配过程怎么走”
• 页面底部的说明文档重点帮助你理解“为什么教材里还会写 next 和 nextval”

建议重点观察什么

可以试试像 ababd、ababaca 这样带有重复结构的模式串。

• 在前缀表区域，观察已经得到的前后缀信息如何被复用
• 在匹配区域，观察失配后为什么不用从头开始

如果你之前只是“背过 KMP”，这个页面最适合帮助你真正理解：

• LPS 到底记录了什么
• 失配时为什么可以跳
• 跳转后为什么不会漏掉正确答案