KMP算法（Knuth-Morris-Pratt）的失效函数（Failure Function）计算 知识点描述 KMP算法是一种高效的字符串匹配算法，其核心思想是通过预处理模式串（Pattern）生成一个称为"失效函数"（也称为部分匹配表或next数组）的辅助数组。该函数记录模式串中前缀与后缀的最长公共长度，使得在匹配失败时，模式串可以跳过不必要的比较，将指针回溯到合适位置继续匹配。失效函数的正确计算是理解KMP算法的关键。 详细讲解 失效函数的作用 在字符串匹配过程中，当主串（Text）与模式串的某个字符不匹配时，失效函数指示模式串应向右滑动多少位，并直接从某个位置继续比较，避免主串指针回退。 失效函数 next[i] 定义为：对于模式串 P[0..i] ，其最长相同真前缀和真后缀的长度（真前缀/后缀指不包括字符串本身的前缀/后缀）。例如，模式串 "ABABC" 的 next[2] 对应子串 "ABA" ，其最长公共真前后缀为 "A" ，长度为1。 计算步骤（递推法） 假设模式串为 P ，长度为 m ，失效函数数组为 next （索引从0开始）： 初始化 ： next[0] = -1 （长度为1的子串无真前后缀，定义为-1便于后续操作）。 设置两个指针： i = 0 （当前子串的末尾索引）， j = -1 （指向当前最长公共前后缀的末尾）。 递推过程 （遍历 i 从 1 到 m-1 ）： 情况1 ：若 j == -1 或 P[i] == P[j] ，说明可延长公共前后缀，则 next[i+1] = j + 1 ，同时 i 和 j 均右移（ i++ , j++ ）。 情况2 ：若 P[i] != P[j] ，则 j 回退到 next[j] （利用已计算的结果缩小比较范围），直到匹配或 j == -1 。 此过程确保每个字符最多比较两次，时间复杂度为O(m)。 示例演示 以模式串 P = "ABABC" 为例： i=0, j=-1 ： next[0]=-1 ； i=1, j=-1 ：满足情况1， next[1]=0 ， i=2, j=0 ； i=2, j=0 ：比较 P[2]='A' 与 P[0]='A' ，匹配， next[2]=1 ， i=3, j=1 ； i=3, j=1 ：比较 P[3]='B' 与 P[1]='B' ，匹配， next[3]=2 ， i=4, j=2 ； i=4, j=2 ：比较 P[4]='C' 与 P[2]='A' ，不匹配， j 回退至 next[2]=1 ；再比较 P[4] 与 P[1] ，不匹配， j 回退至 next[1]=0 ；继续比较 P[4] 与 P[0] ，不匹配， j 回退至 next[0]=-1 ；此时满足情况1， next[4]=0 。 最终 next = [-1, 0, 1, 2, 0] 。 在KMP匹配中的应用 主串指针 t 不回溯，模式串指针 p 根据 next 数组调整： 若 p == -1 或当前字符匹配，则 t 和 p 均右移； 若字符不匹配，则 p 回退到 next[p] 。 例如，主串 "ABABABC" 匹配模式串 "ABABC" 时，在 p=4 （字符 'C' ）处失配，根据 next[4]=0 ，模式串右移使 p=0 继续与主串当前字符比较。 总结 失效函数通过预处理模式串的前后缀信息，将匹配过程优化至O(n+m)。其计算中的指针回退策略是递推效率的保证，需熟练掌握递推条件与边界处理。