题目
求模式串 p = "abacaba" 的 next 数组。按
最长相等真前后缀的定义，答案是
[0,0,1,0,1,2,3]。
⚠️ 一句话先记住：
面试前必须确认面试官用的是哪种定义。另有一种把首项记作
-1 的定义（严蔚敏《数据结构》风格），同一条串在那套定义下的答案是
[-1,0,0,1,0,1,2] —— 两种定义只差一次整体移位，但
报出来的数字完全不同，报错了就是零分。
p = a b a c a b a
next = 0 0 1 0 1 2 3 ← 最长相等真前后缀（本文默认）
另一种 = -1 0 0 1 0 1 2 ← 首项为 -1 的定义
这题看上去只是"背个模板"，真正的门槛却在一处很容易被含糊带过的地方：
next[i] 到底统计的是哪一段子串的前后缀。定义含糊一点（把"真"字漏掉、把"含不含自己"混了），答案就会整体错位；而算出 next 之后，
next[j-1] 那个下标更是
每一次回退的依据。
一、核心洞察：next 是什么，为什么能"自己跟自己比"
先把定义钉死。
next[i] = 子串
p[0..i] 的
最长相等真前后缀的长度。
"
真"字是关键：前后缀都
不能是整个子串本身，长度必须严格小于
i + 1。正因为排除了"整串等于整串"这种平凡情况，
next[0] = 0 是
恒成立的（长度为 1 的子串不存在真前后缀）。
p[0..2] = "aba"：前缀 "a" 与后缀 "a" 相等，长度 1 → next[2] = 1；p[0..3] = "abac"："a" 对 "c"、"ab" 对 "ac" 都不等 → next[3] = 0；p[0..6] = "abacaba"："aba" 前后都出现，长度 3 → next[6] = 3。
最直白的做法是：
对每个 i，从大到小枚举前后缀长度试到相等为止。那是 O(n²) —— 对
n 个位置各扫一遍。KMP 的做法只有一句话：
让模式串跟自己匹配：把 p 同时当成"主串"和"模式串"，i 在主串上走，j 记"已匹配的前缀长度"。
next[0] = 0; j = 0
for i = 1 .. n-1:
while j > 0 且 p[i] != p[j]: j = next[j-1] # 失配：退到更短的候选前缀
if p[i] == p[j]: j = j + 1 # 相等：候选前缀再长一位
next[i] = j
j 有
两副面孔，理解这两副面孔，整段代码就不需要背：
- "已匹配前缀的长度" —— 进入比较前，恒有
p[0 .. j-1] == p[i-j .. i-1]
前
j 个字符与"紧挨着
i 之前的那
j 个字符"逐字相等。这条不变量是全部推导的地基。
2.
"下一个要和 p[i] 比的 p 下标" —— 因为前
j 个字符已经和
p[i-j..i-1] 对齐了，接下来自然该拿
p[j] 去接
p[i]。
def prefix_function(p):
n = len(p)
next = [0] * n
j = 0
for i in range(1, n):
while j > 0 and p[i] != p[j]:
j = next[j - 1] # 失配：退到「更短但仍接得上」的候选前缀
if p[i] == p[j]:
j += 1 # 相等：候选前缀再长一位
next[i] = j
return next
# p = "abacaba" → [0, 0, 1, 0, 1, 2, 3]
三个细节决定了成败：
next[0] = 0 是定义、不用算：循环从 i = 1 开始，省掉一次无意义的比较。- 回退读的是
next[j-1]，不是 next[j]：p[0..j-1] 自身的最长相等前后缀（长度记在 next[j-1] 里）正是"接得上、又更短"的那个候选。用 next[j] 就错位了一格。
- 回退是
while 不是 if：一次退不到底就要接着退。i = 3 那一帧只退了一次，但长串上可能连退好几次。
一句话记住这台机器：
j 是"已匹配前缀长度"，p[0..j-1] 与 p[i-j..i-1] 永远对齐；失配就沿 next[j-1] 往回收，相等就让 j 长一位，收尾把 next[i] = j 记下来。
二、两种定义（面试第一坑）
同一台机器，两种记账方式。
先看表，再作答。
两者的关系干净得只有一句话：
也就是把 A
整体右移一格，再在首位补一个
-1。逐项验证：
B[1] = A[0] = 0、
B[2] = A[1] = 0、
B[3] = A[2] = 1 …… 一直到
B[6] = A[5] = 2，正好是
[-1,0,0,1,0,1,2]。
为什么会有人用 B？因为它把"
失配时 j 该退到哪"直接编进了数组：
- 用 A 时，失配后的动作是
j = next[j-1]（退完再比，j 可能落到 0）；
- 用 B 时，失配后的动作是
j = next[j]，而 B[0] = -1 这个哨兵顺手把"已经退无可退"也表达出来了。
代价是 B 在下标上多绕一层：
B[i] 描述的是
p[0..i-1]，而 A 的
A[i] 描述的就是
p[0..i] 自己。
结论只有一条：
开口先问"您用的是哪种定义"，再动手。可以用这一句把主动权拿回来 ——
"next 有两种常见定义：一种是前缀函数，next[i] 是 p[0..i] 的最长相等真前后缀，next[0] = 0，答案是 [0,0,1,0,1,2,3]；另一种首项取 -1，next[i] 描述 p[0..i-1]，答案是 [-1,0,0,1,0,1,2]。两者只差一次整体移位。我按前一种讲，需要的话可以立刻换成后一种。"
三、动画怎么看
动画一（
algo-viz--kmp）：上面一行是模式串
p 的格子（每格一个字符 + 下标），紧挨着下面一行是
next 数组 —— 还没算出来的格子画成
虚线框 + 灰点，算出来的染绿。
p 行下挂三枚 chip：橙色
i 指当前字符，金色
j 指"已匹配前缀长度"（也就是下一个要跟
p[i] 比的下标），回退帧再多一枚绿
j 落到新位置。每帧一条动作：比较帧把
p[i]、
p[j] 描橙框（相等则染绿），并把
已匹配的那一段前后缀（
p[0..j-1] 与
p[i-j..i-1]）整段刷绿；回退帧用一条
虚线从 p[j] 连到 next[j-1] 那一格；落定帧把
next[i] 染金。下方是横幅 + 五项统计面板（
i /
j / 比较次数 / 回退次数 / 已定 next）+ 状态行。
盯住三件事：
比较帧里 j 一动不动 ——
j 的进退只在落定帧发生；
回退帧是唯一让 j 变小的时刻，且它读的一定是
next[j-1] 那一格（虚线指过去的就是它）；以及
next[0] = 0 那一格从一开始就是绿的 —— 它是定义，不是算出来的。默认 16 帧走完，
next = [0, 0, 1, 0, 1, 2, 3]，全程 7 次比较、1 次回退。
动画二（
algo-viz--kmpmatch）：主串
text 一行、模式串
p 一行，
p 整行按 j 滑动对齐 —— 于是
p[j] 恰好落在
text[i] 正下方，"已匹配前缀"整段对齐一目了然。比较帧把
text[i]、
p[j] 描橙框（相等染绿）；回退帧在
p 行画一条
虚线弧从旧
j 指到新
j，同时
把 text[i] 的橙框留在原地 —— 这就是"
i 不动"的视觉证据；命中帧把
text[index..index+n-1] 与整条
p 染金。面板五项是
i /
j / KMP 比较 / 暴力比较 / 命中下标，其中"暴力比较"是同一输入上暴力匹配
要花的总次数（静态算出来的参照系），整局不变。
两个动画分工明确：动画一
算表（把 next 一个字一个字顶出来），动画二
用表（拿这张 next 去
text 里找
p，并把 KMP 与暴力的账现场对一遍）。
四、完整推演表
动画一：
p = "abacaba"（
n = 7），逐帧走一遍。每条
i 一行的"动作序列"就是那几帧。
i = 3 是全程唯一的回退帧：
p[3] = 'c' 撞上
p[1] = 'b'，
j 从 1 退到
next[0] = 0，换了条更短的候选前缀接着比。它退不下去（
j 已到 0）才定
next[3] = 0。
最终表：
转换成"首项
-1"的定义：
B = [-1] + A[0..5] = [-1, 0, 0, 1, 0, 1, 2]。
动画二：主串
text = "abababacaba"（
m = 11），模式串
p = "abacaba"（
n = 7），借动画一算好的
next = [0, 0, 1, 0, 1, 2, 3]。
两次回退都发生在"
text 里
b 撞上
p[3] = 'c'"的位置上。注意
j 退而不乱：退到 1 之后立刻用
p[1] = 'b' 接住了同一个
text[i] = 'b'，一步没白走 —— 省下的正是
p[0..2] = "aba" 这个已匹配段里
本来就藏着的相等前后缀（
"a"）。
账本对比（同一输入，暴力循环到命中为止）：
KMP 只用
13 次比较就拿到同一个答案
index = 4。省下的是
s = 1、
s = 3 那两次"从头重比"，以及
s = 2 时不用重比
"ab"。规模上的差别会随串长放大：
text = "aaaa…ab"、
p = "aaaa…a" 是经典最坏例，暴力每个起点都要比到最后一个字符，总共 O(n × m) 级；KMP 因为
i 一路向前，一趟就走完。
五、同族题：LC 28 / 459 / 214 / 1392 / 686
KMP 的全部内容其实就是
"一张 next 表 + 一次永不回头的扫描"。同一副骨架换个问法，就是一条完整的题链：
- LC 28 找出字符串中第一个匹配项的下标（
strStr()）：就是动画二本身，标准库里的 indexOf 底层。最经典的同族。
- LC 459 重复的子字符串：不用真的去匹配，直接看 next ——
n 能被周期周长整除时成立，判据是 n % (n - next[n-1]) == 0 且 next[n-1] > 0。它问的是"next 表结构说明了什么"。
- LC 214 最短回文串：把
s + '#' + reverse(s) 拼起来求 next，最长回文前缀的长度就是 next 最后一项 —— 换的是"用 next 找最长回文前缀"。
- LC 1392 最长快乐前缀：字面定义就是
next[n-1]（既是前缀又是后缀的最长子串），一条 next 直接交卷。
- LC 686 重复叠加字符串匹配：允许把
a 重复叠加若干次再匹配 b，匹配次数上界由长度关系定死 —— 换的是"主串可以现场构造"。
把它们排成一列看：
"表"永远是 next 表（或它的变体 Z 函数、失配后的 border 链）；"用"永远是一次不回头的扫描；而问题可以问"第几处出现"、"能不能由周期拼成"、"最长回文前缀多长"、"最长的既是前缀又是后缀的子串"。 next 表只是这条坐标轴上一个入口。
六、Java 版
class Solution {
// 动画一的骨架：求 next 数组（前缀函数）—— 与推演表逐帧一致
public int[] prefixFunction(String p) {
int n = p.length();
int[] next = new int[n];
int j = 0;
for (int i = 1; i < n; i++) {
while (j > 0 && p.charAt(i) != p.charAt(j)) {
j = next[j - 1]; // 失配：退到更短、但仍接得上的候选前缀
}
if (p.charAt(i) == p.charAt(j)) {
j++; // 相等：候选前缀再长一位
}
next[i] = j; // 落定，j 也顺手成了下一个「已匹配长度」
}
return next;
}
}
class Solution {
// 动画二：用 next 在 text 里找 p 的第一次出现，返回起点下标，找不到 -1
public int strStr(String text, String p) {
int m = text.length(), n = p.length();
if (n == 0) return 0;
int[] next = prefixFunction(p);
int j = 0;
for (int i = 0; i < m; i++) {
while (j > 0 && text.charAt(i) != p.charAt(j)) {
j = next[j - 1]; // 失配：主串指针 i 一动不动，只回退 j
}
if (text.charAt(i) == p.charAt(j)) {
j++;
}
if (j == n) {
return i - n + 1; // 命中：起点 = i - n + 1
}
}
return -1; // 扫完未命中
}
private int[] prefixFunction(String p) {
int n = p.length();
int[] next = new int[n];
int j = 0;
for (int i = 1; i < n; i++) {
while (j > 0 && p.charAt(i) != p.charAt(j)) j = next[j - 1];
if (p.charAt(i) == p.charAt(j)) j++;
next[i] = j;
}
return next;
}
}
顺手把"首项
-1"的定义也写出来 —— 一旦面试官说"我用的是
-1 那版"，改的就是
两处下标：
class Solution {
// 另一种定义：next[0] = -1，语义是「p[0..i-1] 的最长相等真前后缀长度」
// 关系：B = [-1] + A[0 .. n-2]，即 B[i] = A[i-1]
public int[] prefixFunctionNegOne(String p) {
int n = p.length();
int[] b = new int[n];
b[0] = -1; // 哨兵
int j = -1;
for (int i = 1; i < n; i++) {
while (j >= 0 && p.charAt(i) != p.charAt(j + 1)) {
j = b[j]; // 注意：退到 b[j]，不是 b[j-1]
}
if (p.charAt(i) == p.charAt(j + 1)) {
j++;
}
b[i] = j;
}
return b; // "abacaba" → [-1, 0, 0, 1, 0, 1, 2]
}
}
两个写法值得单独对比着记：A 版的下标是"
长度"（
j 就是已匹配前缀的长度，
p[j] 是下一个待比字符），B 版的下标是"
位置"（
j 指向最后一个已匹配字符，
p[j + 1] 才是待比字符）。
但两条串出来的表只差一次整体移位。
七、边界情况
- 单字符串：
p = "a" → next = [0]。长度为 1 没有真前后缀，next[0] 永远是 0，一行代码都不用跑。
- 全同串：
p = "aaaa" → next = [0, 1, 2, 3]。每多一个字符，前后缀长度就长一位，j 一路自增、一次回退也没有。
- 完全无相等前后缀：
p = "abcd" → next = [0, 0, 0, 0]。j 每次都在"退到 0 之后仍不等"里收场。
next[i] 的上界是 i：因为"真"排除了整串本身。若某个实现算出 next[i] = i + 1，说明"真"这个约束被漏掉了。- 匹配未命中 → 返回
-1：不是"返回 0"，也不是"返回最后一个位置"。j 从头到尾没到过 n，就是 -1。
- 模式串比主串长：
n > m 直接不可能命中（除了 n = 0 的退化情形），循环会自然扫空。
- 空模式串：约定
n = 0 时 strStr 返回 0（空串是任何串的前缀），next 是空数组。面试里属于"要先跟面试官对齐"的约定项。
text 与 p 有非 ASCII 字符：charAt 按 UTF-16 码元比较，对 BMP 内的字符没问题；超出 BMP 的字符要按码点遍历。这是实现层的坑，不是算法本身的坑。
八、复杂度
n 是模式串长度、
m 是主串长度。
O(n) 这一步的论证是
均摊的，值得背下来：
j 在每一轮循环里最多自增 1（只在 if 相等那一支），所以整个循环里 j 的自增总量不超过 n；而 j 的回退是把自增值还回去，总量自然也不超过自增总量。于是 while 的总执行次数是 O(n) —— 单次循环最坏能退到 0，但整轮加起来是线性的。
匹配段同理：
i 只增不减（
m 步），
j 的回退总量不超过它在匹配过程中自增的总量（
≤ m），所以
O(n + m)。
九、常见坑
- 漏掉"真"字：把子串本身也算作前后缀，
next[i] 会变成 i + 1，回退逻辑随之死循环。本题的头号坑 —— 定义里"真"这个约束就是全部。
- 回退写成
j = next[j]（本文 A 定义下）：应该读 next[j-1]。差这一格会让 j 退到错误的候选上，答案整体错位。
- 回退用
if 而不是 while：一次退不干净。i = 3 那帧只退一次只是巧合，长串上可能连退多次才落定。
- 两种定义混着写：A 版的比较对象是
p[j]、回退读 next[j-1]；B 版比较对象是 p[j+1]、回退读 next[j]。混用会同时错掉比较和回退两处。
- 匹配时让
i 回退：一旦写 i = i - j + 1 重来，就退化成暴力 O(n × m)，KMP 的唯一价值（i 永不回头）当场归零。
- 每轮都重算一遍 next：next 只依赖模式串，算一次反复用。匹配过程里重算是最常见的一种"白送复杂度"。
next 数组下标越界：求 next 时 j < i ≤ n - 1，p[j] 安全；匹配时若 j 已等于 n 还去读 p[j] 就越界了 —— 命中判定要在读之前做。- 把
next[i] 理解成"p[0..i-1]"：那是 B 定义。本文 A 定义下 next[i] 描述的就是 p[0..i] 自己。
十、面试怎么答
第一段 · 先问定义：开口就确认用哪种 —— "前缀函数定义下
next[i] 是
p[0..i] 的最长相等真前后缀、
next[0] = 0，答案是
[0,0,1,0,1,2,3]；若用首项
-1 的那版，答案是
[-1,0,0,1,0,1,2]，两者差一次整体移位。"这一句既展示了你
知道有两种定义，又把选择权交回给面试官。
第二段 · 讲清机器：
next[0] = 0 是定义；从
i = 1 起"
自己跟自己匹配" ——
j 既是"已匹配前缀长度"，也是"下一个要跟
p[i] 比的下标"；不变量是
p[0..j-1] 与
p[i-j..i-1] 逐字相等；失配就
while 沿
next[j-1] 往回收，相等就让
j 前进一步；收尾
next[i] = j。
第三段 · 说清复杂度为什么是线性的：
j 每次最多自增 1，回退只是把自增值还回去，
均摊下来
while 的总步数是 O(n)。匹配段同理，
i 只增不减，于是
O(n + m)。
追问连跳：
- 把"求 next"换成"
在主串里找第一次出现" → LC 28
strStr()，动画二；
- 问"能不能由某个子串重复拼成" → LC 459，判据
n % (n - next[n-1]) == 0；
- 问"
最长回文前缀" → LC 214，把
s + '#' + reverse(s) 求 next；
- 问"
最长的既前缀又后缀的子串" → LC 1392，答案就是
next[n-1]；
- 问"主串可以现场叠加" → LC 686。
一句话收尾："KMP 只有一台机器 ——
一张 next 表 + 一次永不回头的扫描。next 是'自己跟自己匹配'攒出来的边界信息，扫描时靠它把'已匹配段里本来就有的相等前后缀'直接兑现，于是
i 永不回退、总代价
O(n + m)。
两种定义只是同一张表的两种记账方式：
B = [-1] + A[0..n-2]。"
结语
这道题的"难"不在代码 —— 模板只有六行 —— 而在
定义。
next[i] 描述的到底是
p[0..i] 还是
p[0..i-1]、首位是
0 还是
-1，这两问决定了报出来的数字是
[0,0,1,0,1,2,3] 还是
[-1,0,0,1,0,1,2]。
面试里先把定义问清楚，再动手，比背模板有用得多。
剩下的一件事就是把"自己跟自己比"这句话真正看懂：
j 一边记着"已匹配前缀长度"，一边示意"下一个要跟谁比"；失配时沿
next[j-1] 往回收，收的是更短但仍接得上的候选。等这张表攒完，拿它去
text 里扫一遍，
i 一次都不用回头 ——
O(n) 攒表、
O(n + m) 匹配，KMP 买到的就是这两件事。
下一篇见。