KMP算法（字符串匹配）的失效函数（Failure Function）计算
你提到的已讲过题目中确实包含了KMP算法的失效函数，但作为面试中高频出现的核心难点，我打算用更细致的拆解方式重新讲解，确保你能透彻理解其精妙之处。
一、 题目描述
在KMP（Knuth-Morris-Pratt）算法中，失效函数（Failure Function，通常表示为next数组或lps数组）是该算法的灵魂。它用于在模式串与主串匹配失败时，告诉我们模式串可以跳过多少个字符，从哪个位置开始重新尝试匹配，而无需回退主串的指针。
核心问题：给定一个模式串P（长度为m），如何高效、正确地计算出其失效函数next[0...m-1]？
二、 核心思想与直观理解
在讲解计算过程前，必须深刻理解next数组的定义。
1. 定义
next[i] 表示模式串P[0..i]这个前缀子串中，最长的、相等的、真前缀和真后缀的长度。
- 前缀：从第一个字符开始，但不包含最后一个字符的所有连续子串。例如，
"aba"的前缀有"a","ab"。 - 后缀：以最后一个字符结尾，但不包含第一个字符的所有连续子串。例如，
"aba"的后缀有"ba","a"。 - 真：指不能是字符串本身。所以
next[i]的值一定小于i+1。 - 最长相等：我们要找的是既是前缀又是后缀的那个子串的最大长度。
2. 举个例子
模式串 P = "ababac"
| i | P[0..i] | 真前缀集合 | 真后缀集合 | 最长相等真前缀/后缀 | next[i] |
含义 |
|---|---|---|---|---|---|---|
| 0 | "a" |
{""} |
{""} |
"" |
0 | 只有一个字符，没有真前/后缀，长度为0 |
| 1 | "ab" |
{"a"} |
{"b"} |
无 | 0 | 前缀"a"≠后缀"b" |
| 2 | "aba" |
{"a", "ab"} |
{"ba", "a"} |
"a" |
1 | 相等的前缀"a"=后缀"a" |
| 3 | "abab" |
{"a", "ab", "aba"} |
{"bab", "ab", "b"} |
"ab" |
2 | 相等的前缀"ab"=后缀"ab" |
| 4 | "ababa" |
{"a", "ab", "aba", "abab"} |
{"baba", "aba", "ba", "a"} |
"aba" |
3 | 相等的前缀"aba"=后缀"aba" |
| 5 | "ababac" |
{"a", "ab", "aba", "abab", "ababa"} |
{"babac", "abac", "bac", "ac", "c"} |
无 | 0 | 没有相等的 |
所以，next = [0, 0, 1, 2, 3, 0]
实际用途：当我们在主串S的某个位置j，与模式串P的i=5（字符'c'）匹配失败时，我们查看next[4] = 3。这意味着P[0..4]="ababa"这个子串的最长相等前后缀长度是3（"aba"）。所以我们无需从P[0]重新匹配，而是可以直接将模式串的P[3]（即'a'）滑动到当前位置j，继续与S[j]比较。因为已知S[j-3..j-1]（即匹配失败前已匹配成功的3个字符）就是"aba"，与模式串滑动后的前3个字符"aba"是相同的，这部分无需再比较。
三、 失效函数的计算过程（逐步推导）
我们不能用上面列举所有前后缀的暴力方法，其复杂度是O(m^3)。KMP的精髓在于用递推的方法，在O(m)时间内计算next数组。
核心观察：计算next[i]时，我们可以利用已经计算好的next[0], next[1], ..., next[i-1]。
步骤1：初始化
next[0] = 0。单个字符的字符串没有真前/后缀。- 设置两个指针：
i = 1：当前正在计算next[i]，代表后缀的末尾索引。len = 0：当前已匹配的最长相等前后缀长度，也恰好指向最长相等前缀的下一个字符的索引。初始时，len = next[0] = 0。
步骤2：主循环（i 从 1 到 m-1）
我们比较P[i]和P[len]。
-
情况A：
P[i] == P[len]- 这说明我们可以在之前匹配的基础上，将相等的长度再扩展一位。
- 操作：
len = len + 1，然后next[i] = len，最后i = i + 1，处理下一个字符。 - 为什么：
len之前代表了P[0..i-1]的最长相等前后缀长度。现在P[i]等于P[len]，意味着P[0..len]（作为前缀）和P[i-len..i]（作为后缀）是相等的，且长度增加了1。
-
情况B：
P[i] != P[len]- 这很棘手。我们不能简单地认为
next[i]=0。我们需要“回退”len指针，找到一个更短的、可能匹配的前缀。 - 如果
len > 0：- 将
len回退到next[len - 1]。然后不移动i，回到比较P[i]和P[new_len]的步骤。 - 为什么：
len当前指向最长相等前缀的下一个字符。既然P[i] != P[len]，我们就放弃当前这个最长的前缀。next[len-1]告诉我们，在P[0..len-1]这个前缀中，次长的相等前后缀长度是多少。我们就从这个次长前缀的下一个字符开始尝试匹配P[i]。这个过程可能迭代多次（len不断回退），直到找到匹配的P[len]，或者len回退到0。
- 将
- 如果
len == 0：- 说明已经回退到头了，没有任何相等前后缀可以扩展。
- 操作：
next[i] = 0，然后i = i + 1，处理下一个字符。
- 这很棘手。我们不能简单地认为
步骤3：举例推演
再次以P = "ababac"为例，m=6。
| i | len | P[i] vs P[len] | 操作 | next[i]赋值 | 最终len | 备注 |
|---|---|---|---|---|---|---|
| 初始化 | 0 | next[0]=0 |
0 | i=1 | ||
| i=1 | len=0 | P[1]='b' vs P[0]='a' |
不匹配，且len=0 | next[1]=0 |
0 | i++ -> 2 |
| i=2 | len=0 | P[2]='a' vs P[0]='a' |
匹配 | len=1, next[2]=1 |
1 | i++ -> 3 |
| i=3 | len=1 | P[3]='b' vs P[1]='b' |
匹配 | len=2, next[3]=2 |
2 | i++ -> 4 |
| i=4 | len=2 | P[4]='a' vs P[2]='a' |
匹配 | len=3, next[4]=3 |
3 | i++ -> 5 |
| i=5 | len=3 | P[5]='c' vs P[3]='b' |
不匹配，且len>0 | len = next[3-1]=next[2]=1 |
1 | i不变 |
| len=1 | P[5]='c' vs P[1]='b' |
不匹配，且len>0 | len = next[1-1]=next[0]=0 |
0 | i不变 | |
| len=0 | P[5]='c' vs P[0]='a' |
不匹配，且len=0 | next[5]=0 |
0 | i++ -> 6 (结束) |
最终得到next = [0, 0, 1, 2, 3, 0]，与手动分析一致。
四、 代码实现（Python）
def compute_next(pattern: str):
m = len(pattern)
next_array = [0] * m
length = 0 # 当前最长相等前后缀的长度
i = 1
while i < m:
if pattern[i] == pattern[length]:
length += 1
next_array[i] = length
i += 1
else:
if length != 0:
# 关键回退步骤
length = next_array[length - 1]
else:
next_array[i] = 0
i += 1
return next_array
# 测试
pattern = "ababac"
print(compute_next(pattern)) # 输出: [0, 0, 1, 2, 3, 0]
五、 复杂度与要点总结
- 时间复杂度：
O(m)。虽然内层有while循环，但每次循环i或len至少有一个增加，而len最多增加m次，减少（回退）的总次数也不会超过m次，所以是线性的。 - 空间复杂度：
O(m)，用于存储next数组。 - 核心要点：
next数组的定义是针对模式串自身前缀的最长相等前后缀长度。- 计算过程是一个**“自我匹配”**的过程，用前缀去匹配后缀。
- 递推思想是关键：
next[i]的计算依赖于next[0..i-1]。 - 最精妙的一步是
len = next[length - 1]，它利用了已计算的next值进行快速回退，避免了暴力枚举。
理解并能够独立推导出next数组的计算过程，是掌握KMP算法的最重要标志。