KMP算法（字符串匹配）的失效函数（Failure Function）计算

KMP算法是一种高效的字符串匹配算法，其核心在于预处理模式串，生成一个被称为“部分匹配表”（Partial Match Table）或“失效函数”（Failure Function）的数组，通常记为next数组。这个数组使得算法在匹配失败时，能够利用已匹配的信息跳过不必要的比较，从而将时间复杂度优化到O(n+m)。

1. 问题背景与直观理解
假设我们需要在长度为n的文本串T中查找长度为m的模式串P。朴素方法在最坏情况下需要O(n*m)。KMP的优化思路是：当T[i]和P[j]不匹配时，我们不总是将j重置为0（从头开始匹配模式串），而是尝试找到一种方法，利用已匹配的部分来决定j可以回退到一个更“安全”的位置，使得P[0..k] 仍然能和当前文本窗口的末尾部分对齐。这个“安全”位置的信息，就存储在next数组中。

2. 失效函数（next数组）的精确定义
next[j]表示：在模式串P中，以位置j结尾的子串（不包括整个P[0..j]），其“最长的相等真前缀和真后缀”的长度。

• 真前缀/后缀：指不包括字符串本身的前缀/后缀。
• 长度：这个相等的真前缀（也就是相等的真后缀）的长度。
• 公式化定义：next[j] = max{ k | 0 <= k < j, 且 P[0..k-1] == P[j-k..j-1] }。如果这样的k不存在，则next[j] = 0。
• 特别约定：next[0] = -1（方便编程，表示当模式串第一个字符就不匹配时，应将模式串整体右移一位，即i++，j重置为0）。

3. 计算next数组的递推过程
我们采用动态规划（递推）的思想来计算next数组，核心是利用已知的next[0..j-1]来求next[j]。

步骤详解：
假设我们已经计算好了next[0], next[1], ..., next[j-1]，现在要计算next[j]。令k = next[j-1]。

• 情况A：P[j-1] == P[k]。

  • 这意味着，在P[0..j-2]中，长度为k的真前缀P[0..k-1]和真后缀P[j-1-k..j-2]是相等的。现在，P[j-1]又等于P[k]，那么很自然地将这个相等的前后缀各延长一个字符后依然相等。即P[0..k] == P[j-1-k..j-1]。
  • 因此，以j-1结尾的子串，其最长相等真前后缀的长度就是k+1。所以next[j] = k + 1。

• 情况B：P[j-1] != P[k]。

  • 此时，我们不能简单地延长。但我们可以尝试寻找一个更短的、相等的真前后缀。
  • 我们知道next[k]的值代表了在P[0..k-1]这个子串中，最长的相等真前后缀的长度。设k' = next[k]。那么P[0..k'-1] == P[k-k'..k-1]。
  • 由于我们已知P[0..k-1] == P[j-1-k..j-2]（这是由k = next[j-1]的定义保证的），所以P[j-1-k'..j-2]这部分（它是上面那个相等后缀的一部分）等于P[k-k'..k-1]，而P[k-k'..k-1]又等于P[0..k'-1]。因此，我们得到了一个新的、更短的相等关系：P[0..k'-1] == P[j-1-k'..j-2]。
  • 现在，我们检查P[j-1]是否等于P[k']。如果相等，就回到了情况A，next[j] = k' + 1；如果不相等，我们就继续令k'' = next[k']，重复情况B的过程，直到k变为-1。
  • 如果k回溯到-1，意味着我们找不到任何可用的前缀，那么next[j] = 0。

4. 计算示例（以模式串"ababcabaa"为例）

1. next[0] = -1 (约定)
2. j=1: 看P[0]。没有真前缀/后缀。next[1] = 0。
3. j=2: k = next[1] = 0。检查P[1]('b') 和 P[0]('a')。不等。k = next[0] = -1。回溯结束，next[2] = 0。
4. j=3: k = next[2] = 0。检查P[2]('a') 和 P[0]('a')。相等！next[3] = k+1 = 1。
5. j=4: k = next[3] = 1。检查P[3]('b') 和 P[1]('b')。相等！next[4] = 1+1 = 2。
6. j=5: k = next[4] = 2。检查P[4]('c') 和 P[2]('a')。不等。k = next[2] = 0。检查P[4]('c') 和 P[0]('a')。不等。k = next[0] = -1。回溯结束，next[5] = 0。
7. j=6: k = next[5] = 0。检查P[5]('a') 和 P[0]('a')。相等！next[6] = 0+1 = 1。
8. j=7: k = next[6] = 1。检查P[6]('b') 和 P[1]('b')。相等！next[7] = 1+1 = 2。
9. j=8: k = next[7] = 2。检查P[7]('a') 和 P[2]('a')。相等！next[8] = 2+1 = 3。

最终next数组为：[-1, 0, 0, 1, 2, 0, 1, 2, 3]。

5. 算法实现（伪代码）

def compute_next(pattern: str):
    m = len(pattern)
    next_arr = [0] * m
    next_arr[0] = -1
    j = 0
    k = -1
    while j < m - 1: # 注意循环条件，我们计算的是next[j+1]
        if k == -1 or pattern[j] == pattern[k]:
            j += 1
            k += 1
            # 一个常见的优化点：如果回退后的字符和当前字符相等，可以进一步回退
            # 但严格来说，这是next数组的优化版本（有时称为nextval）。
            # 基础版本如下：
            next_arr[j] = k
        else:
            k = next_arr[k] # 关键的回退步骤
    return next_arr

注意，上面循环中的j和k的角色与递推分析中的略有不同，但逻辑完全等价。这里j是当前要计算next值的位置的前一个位置，k是next[j]的候选值。

总结：next数组的计算是KMP算法的预处理步骤，其核心是自我匹配。它巧妙地利用了模式串自身的结构信息（相等的前后缀），通过递推的方式高效构建。理解next数组的定义和递推关系，是掌握KMP算法的关键。在后续的匹配过程中，当T[i]和P[j]失配时，我们只需令j = next[j]，就可以跳过无效比较，让模式串的P[0..next[j]-1]部分直接对齐到文本串中已匹配的部分，然后从P[next[j]]（优化后可能需要再次检查）或T[i]开始新的比较。