字符串

字符串匹配与 KMP

先看暴力错在哪

在文本 s 里找模式串 p 第一次出现的位置。最直接的写法：

function bruteForce(s, p) {
  for (let i = 0; i + p.length <= s.length; i++) {
    let j = 0;
    while (j < p.length && s[i + j] === p[j]) j++;
    if (j === p.length) return i;
  }
  return -1;
}

O(m × n)。⚠️ 但「慢」不是它最值得说的地方 —— 值得说的是它浪费了什么。

s = "aaaaab"
p = "aaab"

i=0: 比了 aaa，第 4 位失配
i=1: 又从头比 aaa……

第一轮已经知道 s[0..2] 是 aaa 了，第二轮却把这个信息全扔了，从 s[1] 重新开始。文本指针回头了。

⭐ KMP 的全部价值就一句话：让文本指针永不回头。

关键问题：失配时模式串该退到哪

文本指针不回头，就意味着失配时只能移动模式串。退多少？

s = "ababac"
p = "ababc"
              ↑ 在这里失配（s 是 'a'，p 是 'c'）

失配前已经匹配上的部分是 abab。现在要问：

abab 的前缀里，最长的、同时也是它后缀的那一段有多长？

答案是 ab（长度 2）。意思是「已匹配部分的末尾 ab」可以直接当作「模式串开头的 ab」来用 —— 所以模式串指针退到 2 就行，不用退到 0。

📌 这就是 next 数组（也叫 fail / lps）： next[i] = p[0..i] 这一段里，最长的「既是前缀又是后缀」的长度（不能是整段）。

p       =  a  b  a  b  c
next    =  0  0  1  2  0

构造 next 数组

⭐ 这段代码的精妙之处：它用自己来构造自己 —— 求 next[i] 时，靠已经算好的 next[0..i-1] 往回跳。

function buildNext(p) {
  const next = new Array(p.length).fill(0);
  let len = 0;                    // 当前「最长相等前后缀」的长度

  for (let i = 1; i < p.length; i++) {
    // 🚨 失配就往回跳，而不是直接归零
    while (len > 0 && p[i] !== p[len]) len = next[len - 1];

    if (p[i] === p[len]) len++;
    next[i] = len;
  }
  return next;
}

🚨 那个 while 里的 len = next[len - 1] 是全篇最容易写错的一行。很多人写成 len = 0（直接归零）—— 答案在大多数串上仍然是对的，只在有嵌套重复结构的串上才错。

⚠️ 而「大多数」有多多，完全取决于字母表大小（各 2 万个随机串，长度 1~12）：

字母表	next 表出错的比例
2 个字母（a/b）	7.6%
3 个字母	1.9%
5 个字母	0.3%

📌 字母表一大，重复结构就难出现，于是这个 bug 几乎撞不上 —— 用随机小写字母串自测这一行，等于没测。 要暴露它得专门构造 aabaaac 这种「短前缀在长前缀里再出现」的形状。

实测 p = "aabaaac"：

正确        next = [0, 1, 0, 1, 2, 2, 0]
写成 len=0  next = [0, 1, 0, 1, 2, 1, 0]
                                  ↑ 第 6 位：该是 2，得到 1

⚠️ 而且这个错未必导致匹配结果错 —— next 表偏小只是让模式串多退几位，匹配依然正确，只是退化到接近暴力。又一个「结果对、只是慢」的坑。

实测：3 万组随机串对着暴力解校验，两个版本的 kmp 都是全对；其中 next 表确实不同的 151 组，匹配结果一组都没错。 ⭐ 所以这一行的错连对拍都抓不到 —— 唯一的判据是直接比 next 表本身。

主匹配：和构造几乎是同一段代码

function kmp(s, p) {
  if (p.length === 0) return 0;
  const next = buildNext(p);

  let j = 0;                                    // 模式串指针
  for (let i = 0; i < s.length; i++) {          // ⭐ i 只增不减 —— 文本永不回头
    while (j > 0 && s[i] !== p[j]) j = next[j - 1];
    if (s[i] === p[j]) j++;
    if (j === p.length) return i - p.length + 1;
  }
  return -1;
}

⭐ 把它和 buildNext 并排看：结构一模一样。构造 next 就是「用 p 自己匹配 p」。想通这一点，KMP 就不用背了。

复杂度：为什么是 O(m + n)

看起来有嵌套的 while，但 j 的总变化量是有界的：

j 每轮最多 +1，整个过程最多加 n 次
while 里每次都让 j 严格变小，而 j 非负

所以 while 的总执行次数不超过 j 增加的总次数 —— 均摊 O(1)。 ⭐ 这和单调栈、滑动窗口的均摊分析是同一套论证： 看起来是嵌套循环，实际被「某个量只增不减」卡死在线性。

⚠️ 面试里要不要手写 KMP

说实话：大多数情况用内置的就行。JS 有 indexOf / includes，面试官问「找子串」时直接用不会扣分。

KMP 真正会被要求手写的场合有两类：

明确说「不许用内置函数」
题目本身要用到 next 数组的性质（比如「最短回文串」「重复的子字符串」）

📌 所以性价比最高的准备方式是：能说清「文本指针不回头」和「next 是什么」，代码记住 len = next[len-1] 那一行的形状。真让手写时能推出来，比背下来更靠谱 —— 因为构造和匹配是同一段结构。

⭐ 另一条路：把子串变成一个数

KMP 解决的是「一个模式串在文本里的位置」。如果题目要的是「拿很多子串互相比」—— 找重复子串、二分子串长度、判断两段是不是相同 —— KMP 帮不上忙，因为根本没有给定的模式串。

那类题用字符串哈希：把子串映射成一个整数，「相等」就退化成 O(1) 的数值比较。 ⚠️ 它在 JavaScript 里有个 KMP 没有的坑 —— 乘法会悄悄越过 2^53，那一篇里实测了三种踩法。

练习

勾选记录做过哪些，0 / 5 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

28. 找出字符串中第一个匹配项的下标简单KMP 的裸题；也可以直接 indexOf
459. 重复的子字符串简单⭐ 用 next 数组的性质一步判定
214. 最短回文串困难在「s + 反转 s」上求 next，KMP 的巧用
1392. 最长快乐前缀困难直接求整串的最长相等前后缀 = next 的最后一项
796. 旋转字符串简单判断旋转：s+s 里找不找得到 goal

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。