暴力匹配是KMP的起点：逐位对齐，失配就右移一位重来。

绿色是已匹配成功、灰色是被丢弃的部分。跟着红色指针走一遍，看它怎样反复回退、反复重比。

上一页看到暴力匹配失配后把主串指针往回挪，白白重扫一遍。其实失配那一刻，主串和模式串刚比对过的那一段是完全已知的——已知的信息里，就藏着少走回头路的线索。

图示失配瞬间：已匹配部分的头尾有相同前缀，模式串直接滑到前缀对齐处，跳过重复比较。

用 Python 实算模式串 "ababc" 的 next 数组，看清每个位置的最长相等前后缀。

nxt[i] 记录「前 i+1 个字符」里，开头与结尾能重合的最长长度——正是失配时可以跳过的匹配量。

两法都逐位比较，最易混淆的是：失败时谁在动？主串指针 i 的行为是本质区别。

上一页我们定下规矩：主串指针绝不回退。那模式串失配后靠什么对齐？靠的是刚才已经匹配成功的那段——比较过的每个结果都记下来，失配时直接查记忆，而不是重新比一遍。

失配后四步走：查表、滑动、跳过、续比，主串指针始终不回退。

上一页走跳转时，每失配一次才查一次 next 表。能不能更快？把主串拿来之前，所有失配位置的去向就先算好——模式串自己跟自己比，答案提前备好，比较时直接翻答案。

next 数组不用暴力求：用模式串自己匹配自己，拿旧值推新值。

把 next 预处理和主循环合在一起，逐行看记忆力和预知力怎么落到代码上。

两处 k = nxt[...-1] 是同一个动作：失配时不回头，而是查 next 表跳到下一个可能对齐的位置——这就是记忆变预知。

KMP 匹配中主串指针 i 失配后，next 数组决定的是谁的动作？

• ✓暴力匹配的浪费：失败后主串指针回退重比
• ✓已匹配部分的前后缀重叠，决定能跳过多少比较
• ✓next 数组把重叠信息预先算好，查表即跳
• ✓主串指针永不回退，比较次数 O(n+m)
• ✓next 的自匹配构造：KMP 用自己算自己

先自己想五分钟，再看参考答案——答案只是思考的起点。