经典题解析：KMP 的 next 数组到底在记什么，一次讲明白

图 1：本文封面，点明「失配不回头」的主线。

先说明属性：这是一篇经典题解析，题目出自本地历史面试资料（见文末来源说明），与任何公司的当前招聘无关。KMP 是字符串匹配的经典算法，面试官几乎不问「你会不会背」，问的是「next 数组里存的到底是什么」。

想象面试现场，面试官写下：给定主串和模式串，返回模式串首次出现的位置；你答完暴力法，他追问——失配之后主串指针为什么一定要回退？能不能不退？

第一步，先立基准：暴力法的浪费在哪。

暴力匹配用两个指针，主串指针 i 和模式串指针 j 同步右移，一旦失配，i 退回本次起点的下一位，j 归零从头再来。最坏情况下每轮都比到最后一个字符才失败，时间复杂度 O(n·m)。浪费在于：失配之前已经成功比对的那些字符，包含了「接下来哪些位置天然不用比」的信息，而暴力法把它全扔了。

第二步，核心概念：next 数组记的是最长相等前后缀。

next[j] 的定义一句话：模式串前 j 个字符里，最长的「相等真前后缀」的长度。以 ABAB 为例：前缀有 A、AB、ABA，后缀有 B、AB、BAB，其中相等的只有 AB，长度 2，所以 next[4] = 2。注意「真」前后缀——不包括字符串本身，否则答案永远是 j 自己。

这个值有什么用？假设已匹配 ABAB，下一个字符失配。既然 ABAB 的开头两个字符和结尾两个字符相同，那么「结尾的 AB」此刻正对着主串，而「开头的 AB」与它一模一样——把模式串向右滑，让开头的 AB 直接对齐到结尾 AB 的位置，这两个字符天然已经匹配，根本不需要再比。模式串直接从第三个字符继续，主串指针 i 原地不动。

第三步，失配规则：i 不动，j 按 next 回退。

整个 KMP 只有一条规则：失配时令 j = next[j]，重复直到能继续匹配或 j 归零。主串指针从头到尾只向右走，预处理 next 数组耗时 O(m)，匹配过程 O(n)，总计 O(n+m)。这就是「利用历史信息避免回退」——next 数组不是玄学表格，它是一份预计算好的「失配时该信谁」的答案。

图 2：next 数组的含义、失配处理示例与复杂度结论。

第四步，写出可运行的代码。

下面这份实现包含 next 数组构建、KMP 匹配与暴力法交叉复核，用 Node.js 22.15.0 直接运行（node kmp.js）即可：

'use strict';

// 构建 next 数组：next[j] 表示模式串前 j 个字符（p[0..j)）的最长相等前后缀长度
function buildNext(p) {
  const next = new Array(p.length + 1).fill(0);
  let k = 0; // 当前已匹配的最长相等前后缀长度
  for (let j = 2; j <= p.length; j++) {
    while (k > 0 && p[k] !== p[j - 1]) k = next[k];
    if (p[k] === p[j - 1]) k++;
    next[j] = k;
  }
  return next;
}

// KMP 匹配：返回 pattern 在 text 中首次出现的下标，未找到返回 -1
function kmpSearch(text, pattern) {
  if (pattern.length === 0) return 0;
  const next = buildNext(pattern);
  let j = 0; // 已匹配的模式串长度
  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) j = next[j]; // 失配：i 不动，j 按 next 回退
    if (text[i] === pattern[j]) j++;
    if (j === pattern.length) return i - pattern.length + 1;
  }
  return -1;
}

// 暴力匹配作对照
function bruteForce(text, pattern) {
  for (let i = 0; i + pattern.length <= text.length; i++) {
    if (text.slice(i, i + pattern.length) === pattern) return i;
  }
  return -1;
}

console.log('ABABC 的 next 数组:', buildNext('ABABC').join(' '));

const cases = [
  ['ABABDABACDABABCABAB', 'ABABCABAB'],
  ['hello world', 'world'],
  ['aaaaab', 'aaab'],
  ['abc', 'd'],
  ['', 'a'],
];
for (const [text, pattern] of cases) {
  const fast = kmpSearch(text, pattern);
  const check = bruteForce(text, pattern);
  console.log(`text="${text}" pattern="${pattern}" -> KMP ${fast}，暴力复核 ${check}`);
  if (fast !== check) throw new Error('两种方法结果不一致');
}

实测输出如下：

ABABC 的 next 数组: 0 0 0 1 2 0
text="ABABDABACDABABCABAB" pattern="ABABCABAB" -> KMP 10，暴力复核 10
text="hello world" pattern="world" -> KMP 6，暴力复核 6
text="aaaaab" pattern="aaab" -> KMP 2，暴力复核 2
text="abc" pattern="d" -> KMP -1，暴力复核 -1
text="" pattern="a" -> KMP -1，暴力复核 -1

五个用例两种方法全部一致，覆盖了模式串含重复前缀、主串为空、完全不匹配三个边界。

易错点清单。

一，把 next 数组背成数字却讲不出「最长相等前后缀」的定义。二，忘了「真」前后缀不含字符串自身，ABAB 的答案说成 4。三，失配时让主串指针回退——那就退化回暴力法，KMP 的灵魂是 i 不动。四，next 数组的下标口径混乱：有人按「前 j 个字符」定义，有人按「第 j 个字符」定义，两种写法差一位，面试时先说清自己的口径再写代码。五，构建 next 时忘记失配要继续沿 next 链回退，只回退一次导致结果错误。

回到面试现场，建议的答题节奏：先给暴力法并指出「已匹配信息被丢弃」，再给出 next 数组的定义并举例，然后讲失配规则「i 不动、j 按 next 回退」，最后写代码并交代复杂度。日志模式匹配、敏感词过滤、流式文本处理，背后都是这同一个思想。

如果面试官追问「要找出模式串出现的所有位置，而不是第一个」，代码只需改动哪几行？欢迎写出你的答案。

参考资料

• Node.js v22.x 官方 API 文档（文中代码运行环境为 Node.js 22.15.0，Array.prototype.fill、String.prototype.slice 等行为以此为准） — https://nodejs.org/docs/latest-v22.x/api/