KMP算法（Knuth-Morris-Pratt）的失效函数（Failure Function）计算 KMP算法是一种高效的字符串匹配算法，其核心在于通过预处理模式串（Pattern）生成一个称为 部分匹配表 （Partial Match Table）或 失效函数（Failure Function） 的数组，从而在匹配失败时避免回溯主串（Text）的指针。下面我们重点讲解失效函数的计算过程。 1. 失效函数的作用 失效函数（通常记为 next 数组或 lps 数组）用于记录模式串中每个位置之前的子串的 最长公共前后缀 （Longest Proper Prefix which is also a Suffix）的长度。 前缀 ：不包含最后一个字符的子串（如"abc"的前缀有"a", "ab"）。 后缀 ：不包含第一个字符的子串（如"abc"的后缀有"c", "bc"）。 最长公共前后缀 ：指同一个子串的前缀和后缀中完全相同的部分的最大长度。 示例 ： 模式串 P = "ababc" 位置 i=0 （子串 "a" ）：无公共前后缀，长度为 0。 位置 i=1 （子串 "ab" ）：前缀 "a" ，后缀 "b" ，无公共部分，长度为 0。 位置 i=2 （子串 "aba" ）：前缀 "a" 与后缀 "a" 相同，长度为 1。 位置 i=3 （子串 "abab" ）：前缀 "ab" 与后缀 "ab" 相同，长度为 2。 位置 i=4 （子串 "ababc" ）：无公共前后缀，长度为 0。 失效函数数组为 next = [0, 0, 1, 2, 0] 。 2. 失效函数的计算步骤 失效函数的计算通过动态规划思想完成，定义两个指针： i ：遍历模式串的指针（从 1 开始），表示当前计算的位置。 j ：指向前缀的末尾位置，同时表示当前最长公共前后缀的长度。 算法步骤 ： 初始化 next[0] = 0 ， j = 0 ， i = 1 。 循环遍历 i 从 1 到模式串长度减 1： 情况1 ：若 P[i] == P[j] ，说明公共前后缀可扩展，令 j++ ， next[i] = j ， i++ 。 情况2 ：若 P[i] != P[j] 且 j > 0 ，则回溯 j = next[j-1] （利用已计算的结果避免重复匹配）。 情况3 ：若 P[i] != P[j] 且 j == 0 ，说明无公共前后缀， next[i] = 0 ， i++ 。 示例 ：以 P = "ababc" 为例： i=1, j=0 ： P[1]='b' != P[0]='a' ，且 j=0 ， next[1]=0 ， i=2 。 i=2, j=0 ： P[2]='a' == P[0]='a' ， j=1 ， next[2]=1 ， i=3 。 i=3, j=1 ： P[3]='b' == P[1]='b' ， j=2 ， next[3]=2 ， i=4 。 i=4, j=2 ： P[4]='c' != P[2]='a' ，回溯 j = next[1] = 0 。 此时 j=0 ， P[4]='c' != P[0]='a' ， next[4]=0 。 最终 next = [0, 0, 1, 2, 0] 。 3. 为什么失效函数能优化匹配？ 在匹配过程中，当主串 T 和模式串 P 在位置 i 和 j 失配时，KMP算法不会回溯主串指针，而是将 P 的指针移动到 next[j-1] 的位置继续匹配。这是因为 next[j-1] 记录了 P[0..j-1] 的最长公共前后缀长度，直接跳过已匹配的前缀部分，避免重复比较。 匹配示例 ： 主串 T = "abababc" ，模式串 P = "ababc" ， next = [0,0,1,2,0] 。 匹配到 T[4]='a' 和 P[4]='c' 失配。 查 next[3]=2 ，将 P 的指针移动到位置 2（ P[2]='a' ），继续与 T[4]='a' 比较。 匹配成功。 4. 时间复杂度分析 计算失效函数：O(m)（m为模式串长度），因 i 和 j 的移动总次数不超过 2m。 匹配过程：O(n)（n为主串长度）。 总复杂度：O(n + m)，远优于朴素算法的 O(n* m)。 5. 常见误区与注意事项 失效函数的值 不包括整个子串本身 （即要求是真前缀/真后缀）。 回溯时 j = next[j-1] 而非 j = j-1 ，确保跳转到最长公共前后缀的末尾。 不同实现中 next 数组的索引可能从 0 或 1 开始，但核心逻辑一致。 通过理解失效函数的计算和匹配机制，可以深入掌握KMP算法的高效性，并灵活应用于字符串匹配问题中。