KMP之前先看暴力匹配：逐位比较，失配就右移一格重来。

上一页我们看到暴力匹配能跑通，但主串指针 i 匹配失败后要退回去重新数。就像读一本书读到一半忘了页码，只能翻回第一页重读——问题到底出在哪两处？

模式串在位置 j 失配时，已匹配的前缀中藏着哪条可直接利用的信息？

上页我们说了失配后不必从头比。那到底能跳多远？答案藏在失配点之前的那段已匹配文本里——看它的开头和结尾有多少是「重复」的。

沿箭头走一遍失配流程：j 处失配后，查表、跳跃、原地继续比，主串指针永不回头。

用 next[] 表重跑同一组匹配：主串指针 i 永不回退，失配时只有模式串指针 j 跳到 next[j]。

失配时 j=next[j-1]，利用已匹配前缀的公共前后缀直接对齐，主串指针 i 从不回头——这正是相对暴力匹配省时的全部来源。

两者失配时都动模式串指针，但主串指针是否回退，是初学最容易混淆的关键差异。

上一页我们看到：KMP 的主串指针从不后退。凭什么敢不回头？因为失配那一刻，已匹配的前缀本身携带了结构信息——next[] 表已经把这段信息「吸收」干净，主串不需要再被看第二遍。

用主串 ABABCABABD 匹配模式 ABABD，逐步验证主串指针从不回头。

走完整个例子后你会发现：KMP 从没让主串指针回头。线性复杂度不是算出来的巧合，而是「主串指针只前进」这一条纪律的直接推论。

按 next[] 跳跃时有个尴尬时刻：模式串开头就失配，j 已经是 0，没有更靠前的位置可跳了。难道要写一段特殊代码处理这种情况？更聪明的做法是——放一个万能哨兵统一收编。

利用「模式串自己匹配自己」递推算出next[]，每一步只依赖前面的结果。

用 Python 逐位计算模式串 "ABABC" 的 next[]，每步打印依据，验证递推构造。

高亮行就是递推构造：k 沿已算好的 next 链回退找可延长的公共前后缀，nxt[i]=k+1 写入答案，输出与手推结果一致。

采用 next[0]=-1 的约定，模式串 "ababaa" 中位置 5（字符 'a'）的 next 值是多少？即前缀 "ababa" 的答案。

• ✓主串指针只进不退，回溯全交给模式串
• ✓next[j]=已匹配段最长公共前后缀长度
• ✓哨兵-1把边界情况并入同一套移动逻辑
• ✓构造next本身用递推，均摊O(1)一次比较
• ✓失配跳跃总代价均摊后为O(n+m)

先自己想，别急着翻答案——想不动了再看参考思路。