KMP 查询表
看完你能亲手推导next数组，并说清失配时模式串为何能跳着滑
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
KMP 查询表
看完你能亲手推导next数组，并说清失配时模式串为何能跳着滑
暴力匹配的痛点
上一页我们说 KMP 有张查询表能避免重复比较。但在看这张表之前，得先明白它到底替我们省掉了什么——先回到最朴素的暴力匹配，看看它是怎么在失配时白白浪费工作的。
抄错一整行就撕掉重抄，明明只错最后一个字
核心思路：模式串自匹配
上一页看到暴力匹配一失败就把主串指针往回挪，太浪费。其实想想：已匹配的那段字符完全来自模式串本身，模式串对它了如指掌——那能不能让模式串自己照照镜子，提前算好失败后从哪儿继续？
卡壳时不用重背全文，接上背过的段落末尾继续
next 表的定义
上一页我们发现：失配后其实能从模式串自己身上找回进度。那到底回退到哪？答案可以提前算好存进一张表——next 表。先弄清楚这张表每个位置到底存的是什么。
接棒点提前定好，失配时直接去 next[j] 接着跑
前缀、真前缀与真后缀
先看前缀/后缀如何派生出「真」版本，再用 ABABC 举例，最后汇合到 next 表的取值来源。
next 表递推构造
看 k 如何借已有 next 值回退，O(m) 建出整张表。
失败时不从头比，k 沿 next 链跳到次长候选；成功则 k 加一并写入 nxt[j]，每步都由之前的项推出。
手工推一例 next 表
用模式串 abcabd 亲手递推一遍 next 表，验证构造规则。
小测：next 值
模式串 "abab" 中，next[3]（第 4 个字符 'b' 处）的真前缀-真后缀最长公共长度是多少？
KMP 匹配框架
前面我们花大力气构造了 next 表，但它在匹配时到底怎么用？回忆暴力匹配：失配后文本串指针要往回退，前功尽弃。KMP 的妙处就在失配那一刻只动一个指针。
读到的位置 i 不重读，只调整脑中已记住的进度 j
失配时的动作分解
匹配中每一对字符比较，只有三种结局，逐一拆开看。
KMP 主算法代码
把 next 表和匹配循环拼起来：一段真正能跑的完整 KMP。
build_next 与 kmp_search 共享同一套「失配沿 next 回退、匹配指针前移」逻辑，i 永不回退是线性复杂度的关键。
复杂度：为何是线性
从指针 j 的循环看：它只增不减，n 步内必走完，加上回退的模式串指针，总计 O(n+m)。
暴力 vs KMP
同样是匹配，核心区别只有一个：失配后文本指针动不动。看清这一点，复杂度差距自然浮现。
- 失配后文本指针回退
- 模式串仅移一位重比
- 最坏 O(n·m)，如 AAA 匹配
- 文本指针永不回退
- 按 next 表跳模式串指针
- 最坏 O(n+m)，均摊线性
实例：完整匹配过程
以主串 ABABCABABABD、模式串 ABABABD 为例，完整走一遍失配跳转。
实例中的指针轨迹
跟着 i、j 一步步走：注意每次失配后，i 始终不回退，只有 j 沿 next 跳。
要点收束
- ✓失配时主串指针不回退，是线性的根源
- ✓next[j]＝真前缀与真后缀的最长相等长度
- ✓构造 next 表本身就是模式串自匹配
- ✓next 表让模式串按已知信息滑动，而非从头再来
- ✓均摊分析保证双指针总移动不超过 2n
课后思考
先合上讲义自己推一遍，再回头看参考答案。
参考答案思考路径：失配后 j 不断变小，递推和匹配都依赖 j=-1 时的特殊分支「前进、归零」。若 next[0]=0，j=0 失配会跳回 0，陷入死循环，必须有终止条件兜底。
参考答案能。KMP 每次匹配成功后按 next 值回退 j 再继续，而不是把 i 拉回去，重叠的起始位置会在后续推进中自然被逐一命中。可以拿 AAA/AAAA 手工走一遍验证。
参考答案思考路径：nextval 剔除的是「跳过去后字符仍相等、必然再次失配」的跳转，被跳过的位置本来就不可能成功，因此剪掉冗余不损失解。回顾 next 递推中 s[i] 与 s[j] 相等的分支即可理解。