从左往右看：主串指针 i 一路前进，一旦失配就大幅回退，前面比对过的字符全部白比。

上一页看到暴力匹配会反复回退主串。KMP 的解法是让模式串自己记住：失配时该从哪里继续。这份备忘录就是 next[] 表，先给它一个严格定义。

从左往右看：求 next[j] 时先查一条边是否相等，相等走短路，不等走回退长路。

失配时沿 next 表逐级回退 k，每一步都在找更短的相等前后缀。

以模式串 ABABC 为例，从左到右逐位递推 next[]，每步只看前一位的比较结果。

把前面两页的递推与回退浓缩成一个可运行的构造函数。

while 是失配回退分支（k=nxt[k-1]），if 是匹配延长分支（k+=1），与手工推演的两情形一一对应。

用模式串 ababa 单步执行代码，逐项核对 next[] 的每个值。

追踪 i 与 k 的总移动次数：i 只增不减，k 虽会回退但每次回退都由 i 的前进「付费」，总代价 O(m)。

next[] 最易错的是两个极端：无公共前后缀时取什么、全同字符时为何一路递增。边界值最能检验你是否真懂定义。

模式串 "ababab"，next[1]=0（下标从 1 开始），正确的 next[] 表是？

• ✓next[j] 的本质：真前缀与真后缀的最长相等长度
• ✓递推只用两种情形：相等就延伸，失配就回退
• ✓回退是递归的，但被 next[] 链条天然有序化
• ✓摊还分析保证：双指针均摊各走 O(n) 步
• ✓边界优先想 j=0 与 j=1：递推的锚点

先合上笔记自己想十分钟，再对照参考答案，看思路是否对得上。