🔑 KMP 的失败函数：匹配失败时，别把已经知道的东西忘掉

很多字符串匹配算法慢，不是因为它们不会比较字符，而是因为它们太健忘。比如你在一段文本里找 ababaca，朴素做法一旦中途失败，就把模式串挪一格，从头再比。问题是，前面已经比过的 ababa 不是垃圾信息，它里面藏着一个事实：有些前缀和后缀是一样的。

KMP 的核心就抓住这一点。它会先给模式串做一张小表，通常叫失败函数，或者 next 数组。这个名字听起来像“失败之后怎么办”，其实更准确地说，它记录的是：当匹配到某个位置失败时，模式串可以退回到哪里，而文本指针不用回头。

拿 ababaca 来看，前面的 ababa 里，开头的 aba 和结尾的 aba 是一样的。所以如果下一位匹配失败，没必要把整个模式串清空重来，可以直接把“已经匹配的长度”退到 3。文本没有变，知识没有丢，只是模式串换了一个更聪明的位置继续试。

这就是 KMP 从朴素匹配里省掉的东西：它不是让比较变快，而是拒绝重复比较。朴素算法最坏会反复扫描同一段文本，KMP 则保证文本里的每个字符基本只往前走一次，所以复杂度是 O(n + m)，其中 n 是文本长度，m 是模式串长度。



容易混淆的是，失败函数不是在记录“失败的位置”，而是在记录“当前已匹配内容里，最长的相同前缀和后缀”。这张表一旦想明白，KMP 就不再像玄学；它只是把“别忘掉已经知道的东西”写成了代码。

#CS