故事验钞机的暗记
银行验钞机上有一个小屏幕，要在一张钞票的整条防伪带上找出暗记序列 「金金银金金」。防伪带上的字符是机器随机印上去的，比如 「银金金金金金银金金」。
初级工人的做法是：拿着暗记从头对齐，一个字一个字地对；一旦发现第 5 个字对不上，就把暗记整体右移一格，从第 1 个字重新开始对。
这个办法在「银金金金金金金金金金金金」这种长串上会崩溃 —— 每次都要从头比 4 个字才发现第 5 个不对，白白浪费了大量时间，总比较次数高达 n × m。
老师傅看了一眼说：「你已经知道前 4 个字是金金金金了，那为什么还要重新看一遍？直接把暗记往后挪到下一个可能的位置就行。」
「已经匹配成功的前缀，本身就蕴含了「还能往哪挪」的全部信息。
把这句直觉写成一张表，就是 next 数组；拿着这张表扫描，主串指针永远不回头，复杂度降到 O(n + m)。这就是 KMP。
💡 KMP 到底省掉了什么
朴素匹配里，失配后我们让主串指针回退，然后重新比较已经比较过的那一段。而这一段之所以能匹配上，说明它和模式串的前缀完全相同 —— 这个信息早就在我们手里了。
KMP 的思路是：主串指针 i 只前进、不回头；失配时只把模式串指针 j 往回跳到「下一个可能匹配的位置」。这个「跳到哪里」由模式串自身决定，与主串无关，所以可以预处理成一张表。
一句话总结：KMP = 主串不回退 + 失配跳 next。