文章目录KMP算法详解预测型Next数组最容易理解版前言一、基础概念最长相等前后缀二、预测型next数组定义示例模式串 P ababc三、预测型next数组代码推导核心难点手动走一遍 Pababcnext[-1,0,0,1,2]Python完整next数组构建函数四、KMP匹配主逻辑使用预测型next数组KMP完整匹配代码执行过程简要演示五、next数组优化nextval改进版避免无效跳转六、复杂度分析七、常见误区澄清八、什么时候用KMP结尾小结KMP算法详解预测型Next数组最容易理解版前言KMP全称Knuth-Morris-Pratt是经典的字符串模式匹配算法。暴力匹配BF每次匹配失败后主串指针回退、模式串指针从头重来时间复杂度最坏O ( n ∗ m ) O(n*m)O(n∗m)KMP核心思想匹配失败时主串指针不回退只移动模式串。移动多少距离由next数组决定。很多教程的next数组有两种版本预测型next推荐本文讲解next[j]表示模式串下标j位置匹配失败时模式串指针应该跳到next[j]旧版nextnext[j]代表子串P[0~j-1]的最长相等前后缀长度。本文重点讲预测型next数组也是工程里最常用的版本直接用于匹配跳转。一、基础概念最长相等前后缀前缀不包含最后一个字符的所有以第一个字符开头的连续子串后缀不包含第一个字符的所有以最后一个字符结尾的连续子串最长相等前后缀前缀集合和后缀集合中长度最大的相同子串。举例子模式串P ababc子串abab前缀a,ab,aba后缀b,ab,bab→ 最长相等前后缀是ab长度2。为什么需要最长相等前后缀当P[j]和主串S[i]匹配失败前面已经匹配成功的部分是P[0~j-1]它的最长相等前后缀意味着前缀已经匹配上的部分可以复用不需要从头重新比对。模式串指针直接跳到最长相等前后缀长度的位置这就是KMP跳过无效比对的本质。二、预测型next数组定义预测型 next数组next[j]当模式串P[j]和主串字符匹配失败时模式串指针j要跳转到next[j]位置继续匹配。定义规则预测版next[0] -1模式串第0位匹配失败代表模式串第一个字符就不匹配模式串指针直接跳到-1下一轮i,j相当于模式串从头开始。对于j0next[j]等于子串P[0, j-1]的最长相等前后缀长度。示例模式串P ababcP: 索引0:a 1:b 2:a 3:b 4:c逐个计算nextnext[0] -1j1子串P[0~0] “a”无前后缀最长长度0 →next[1]0j2子串P[0~1] “ab”前缀a后缀b无相等长度0 →next[2]0j3子串P[0~2] “aba”前缀a,ab后缀a,ba最长相等a长度1 →next[3]1j4子串P[0~3] “abab”前缀a,ab,aba后缀b,ab,bab最长相等ab长度2 →next[4]2最终 next数组[-1, 0, 0, 1, 2]✅ 预测型含义如果 j4字符c匹配失败j next[4] 2拿P[2]字符继续和主串当前字符对比。三、预测型next数组代码推导核心难点目标输入模式串P输出next数组。变量说明j当前求next的下标从1开始遍历k记录P[0, j-1]的最长相等前后缀长度next[0] -1初始化初始化 next[0] -1 j 1, k -1 while j len(P): # 情况1k -1 或者 P[j-1] P[k] if k -1 or P[j-1] P[k]: k 1 next[j] k j 1 # 情况2字符不相等k回退找更短的相等前后缀 else: k next[k]手动走一遍 P“ababc”next[-1,0,0,1,2]初始 next[-1], j1, k-1k-1 → k0next[1]0j2P[1]b vs P[0]a 不相等 → knext[0]-1k-1 → k0next[2]0j3P[2]a vs P[0]a 相等 → k1next[3]1j4P[3]b vs P[1]b 相等 → k2next[4]2j5循环结束完美得到结果。重点理解k next[k]当P[j-1] ! P[k]不能直接k–要递归回退到next[k]。含义当前长度k的前后缀不匹配尝试找子前缀内部的最长相等前后缀缩短匹配长度。这就是KMP预处理的精髓。Python完整next数组构建函数defbuild_next(pattern):mlen(pattern)next_arr[-1]*m j1k-1whilejm:ifk-1orpattern[j-1]pattern[k]:k1next_arr[j]k j1else:knext_arr[k]returnnext_arrprint(build_next(ababc))# [-1, 0, 0, 1, 2]四、KMP匹配主逻辑使用预测型next数组主串S模式串Pnext数组已经预处理完成。规则i主串指针j模式串指针S[i] P[j]i, j继续下一位比对S[i] ! P[j]j next[j]预测跳转i不动终止条件i遍历完主串或者 j len§匹配成功返回起始下标i-j当 j-1 时说明模式串第一位都匹配失败i, j模式串从头开始匹配。KMP完整匹配代码defkmp_search(s,pattern):nlen(s)mlen(pattern)ifm0:return0next_arrbuild_next(pattern)i,j0,0whileinandjm:ifj-1ors[i]pattern[j]:i1j1else:jnext_arr[j]ifjm:returni-j# 返回匹配起始位置else:return-1# 未找到print(kmp_search(abababc,ababc))# 输出2执行过程简要演示S abababcPababcnext[-1,0,0,1,2]i,j同步增加直到匹配到S[4]a vs P[4]c字符不等。j next[4] 2拿P[2]继续和S[4]比对继续匹配最后完整匹配成功。五、next数组优化nextval改进版避免无效跳转问题原始预测next数组会出现模式串当前字符和跳转后字符一样导致一次多余失败。例P“aaaaa”next数组[-1,0,1,2,3]当P[4]匹配失败跳到next[4]3P[3]也是’a’依然和主串不匹配需要继续跳。nextval数组如果跳转后的字符等于当前字符继续递归跳转消除重复比较。nextval构建思路defbuild_nextval(pattern,next_arr):mlen(pattern)nextval[0]*m nextval[0]-1forjinrange(1,m):knext_arr[j]whilek!-1andpattern[j]pattern[k]:knext_arr[k]nextval[j]kreturnnextval工程中可选优化基础KMP掌握预测next数组即可。六、复杂度分析预处理next数组KaTeX parse error: Cant use function \( in math mode at position 1: \̲(̲O(m)\)m是模式串长度KMP匹配过程KaTeX parse error: Cant use function \( in math mode at position 1: \̲(̲O(n)\)n为主串长度总时间复杂度KaTeX parse error: Cant use function \( in math mode at position 13: \boldsymbol{\̲(̲\boldsymbol{O(n…空间复杂度KaTeX parse error: Cant use function \( in math mode at position 1: \̲(̲O(m)\)用来存next数组。对比暴力BF最坏O ( n ∗ m ) O(n*m)O(n∗m)大数据量差距巨大。七、常见误区澄清❌ 误区next[j]是P[0~j]的最长相等前后缀长度✅ 预测型next[j]P[0~j-1]的最长相等前后缀长度next[0]强制-1。这是网上很多教程版本混乱的根源❌ 匹配失败后主串指针i回退✅ KMPi永不回退只有j依靠next数组向前跳转。❌ k k-1 来回退✅ 不能直接k-1必须k next[k]递归回退才能找到次长相等前后缀。八、什么时候用KMP长文本多模式匹配、字符串查找编辑器查找、日志检索字符串周期判断利用最长相等前后缀求字符串最小循环节重复子串检测补充现在标准库字符串查找底层不一定是KMP很多用Boyer-Moore、Two-Way算法但KMP是面试必考理解next数组是核心。结尾小结KMP本质一句话预处理模式串得到预测型next数组记录每个位置匹配失败时模式串指针跳转到哪匹配时主串指针不回溯利用已经匹配成功的前缀信息跳过无效比对把复杂度降到线性。预测型next数组关键点next[0]-1next[j]代表P[0~j-1]最长相等前后缀长度构建时不相等则knext[k]递归回退