1. 这一篇到底要解决什么问题距离上一篇聊 KMP 基础已经有一阵子了。上一篇推完了 next 数组的手工推导也用一个简单的文本匹配把流程跑通了当时不少读者留言说“原理明白了一写代码就废”还有人说“感觉自己会了但是换个模式串又算不对 next 数组”。这篇就是冲着这些问题来的。KMP,全称是 Knuth-Morris-Pratt 字符串匹配算法说实话它不是一个“用了就性能翻倍”的银弹但是它在处理“一个主串里反复查同一个模式串”“大量文本里找一个固定关键词”这类场景时效率确实碾压暴力匹配。我算是从学生时代就开始折腾这套算法后来在某公司的日志检索模块里真正把 KMP 用到了生产环境期间踩了不少坑也总结了一套相对稳的写法和排查套路这里分享出来希望能帮卡在“看懂”和“写对”之间的同学跨过这个坎。这篇的重点放在三块一是把 next 数组升级为 nextval 的来龙去脉讲透二是给出能直接抄的工程级实现三是从复杂度、实际性能和常见错误三个角度帮你彻底“排雷”。如果你已经能把 next 数组从纸上推出来但对代码实现和极端情况还没把握这篇就是你的菜。如果你连 next 数组都没搞明白建议先花半小时回顾上一篇不然这篇读起来会有点费劲。2. next数组到nextvalKMP优化中最容易翻车的一段2.1 为什么朴素的next数组还不够很多人在实现了第一版 KMP 之后拿一个复杂的模式串一测就露馅了。比如模式串是aaaaab用原始 next 数组去匹配主串aaaaacaaaaab你会发现虽然整体复杂度还是线性的但中间出现了不少“虽然知道该右移但明明可以跳更多”的冗余移动。这里的根子在于next 数组本身记录的是“最长相同前后缀的长度”但它没考虑一个更关键的问题也就是当失配发生时j回溯到next[j]之后这个位置上的字符会不会依然是导致失配的那个字符。换句话说如果模式串里有大量重复字符你按 next 回退一次之后很可能还是和主串失配的那个字符对比那这次比较就是必然失败的。举个例子模式串aaaaab假设某个时刻在j4的位置失配主串当前字符是c。next[4] 3于是把 j 移到 3但你拿p[3]还是a和c比又是一个失配。然后再移一次再失配。这样来回折腾几次虽然复杂度没有变成平方级但白白浪费了几次字符比较。数据量一大这个损失就很明显。nextval 数组解决的就是这个问题在计算 next 的同时判断回退后的字符是否和当前字符相同如果相同就继续往前回退直到不相同或者退到起点。很多教科书上称它为“优化后的 next 数组”代码实现上也叫nextval。实话说你要是只在笔试里手写 KMP判题数据不刁钻的话普通 next 也能过但做工程优化或者应付严格的面试手撕nextval 几乎是标配。2.2 nextval递推式的推导走查先约定一下下标规则模式串p[0]是第一个字符next 数组和 nextval 数组长度都与模式串长度一致。初始条件很简单nextval[0] -1表示模式串第一个字符就失配时主串指针要前进模式串从头开始。递推的时候核心逻辑分两种情况。第一种p[i] p[j]也就是当前位置的字符能继续匹配上最长相同前后缀那next[i] j 1注意如果此时p[next[i]] ! p[i]那 nextval 就直接继承next[i]的值反过来如果p[next[i]] p[i]说明跳过去之后还要被相同的字符拦住nextval 应该写成nextval[next[i]]而不是next[i]。第二种p[i] ! p[j]那就按经典思路回退 jj nextval[j]直到j -1或p[i] p[j]为止。很多初学同学在这里犯迷糊的是为啥回退的时候也用 nextval而不用 next我个人的理解是回退的目标本来就是找一个“不会做无用功”的位置既然 nextval 已经帮你把同字符跳过的问题过滤掉了那回退用 nextval 自然比用 next 更彻底。拿一个具体例子走一遍。模式串ababc手工推导p: a b a b c i0: nextval[0] -1 i1: j0, p[1]b ! p[0]a, 且 j0, nextval[1] 0 i2: 回溯 j 时发现 p[2]a, 可参考的前后缀拿 j0 比较, p[2]p[0], next[2]1, 再检查 p[next[2]] p[1] b ! a, 所以 nextval[2] 1 i3: j1, p[3]b p[1]b, next[3]2, 检查 p[next[3]] p[2]a, 和当前 p[3]b 不同, nextval[3]2 i4: j2, p[4]c ! p[2]a, 回退 jnextval[2]1, p[4]c ! p[1]b, 回退 jnextval[1]0, p[4]c ! p[0]a, j-1, next[4]0, nextval[4]0走到这里你就能感觉到手工推 nextval 比推 next 多了一个“再判断一步”的动作而这个动作正是减少无用比较的关键。我建议学的时候别直接背代码拿三四个模式串手工推一遍推完再用代码验证印象会深刻很多。3. 完整实现从暴力到KMP再到优化KMP3.1 直接能用的三段式实现每次讲到这都有读者说“原理都会代码写不出来”。与其东拼西凑背网上的代码片段不如老老实实按三段式来写先写构建 nextval 的函数再写匹配主函数最后用最小用例跑通。下面给一个 Python 的版本我只保留了关键逻辑工程上你完全可以直接抄def build_nextval(pattern): m len(pattern) nextval [0] * m nextval[0] -1 j -1 i 0 while i m - 1: if j -1 or pattern[i] pattern[j]: i 1 j 1 if pattern[i] ! pattern[j]: nextval[i] j else: nextval[i] nextval[j] else: j nextval[j] return nextval def kmp_search(text, pattern): n len(text) m len(pattern) if m 0: return 0 nextval build_nextval(pattern) i 0 j 0 while i n: if j -1 or text[i] pattern[j]: i 1 j 1 if j m: return i - j else: j nextval[j] return -1注意看 build_nextval 里的写法我在pattern[i] ! pattern[j]时直接存j相等时存nextval[j]这其实就是上面讲的优化点。匹配函数里也用到了j nextval[j]失配时 j 可能变成 -1此时下一轮会走j -1的分支重置比较位置这也是很多同学容易写漏的边界条件。3.2 用一组数据手工走查验证如果你把上面的代码直接跑一遍得到的结果应该和手工推的一致。下面我完整走查一个主串ababaababc匹配模式串ababcbuild_nextval 算出来i p[i] nextval[i] 0 a -1 1 b 0 2 a 1 3 b 2 4 c 0开始匹配主串: a b a b a a b a b c 模式: a b a b c i0 j0 匹配 a i1 j1 匹配 b i2 j2 匹配 a i3 j3 匹配 b i4 j4 失配, 主串是 a, 模式是 c, jnextval[4]0 i4 j0 匹配 a i5 j1 主串 a 模式 b 失配, jnextval[1]0 i5 j0 匹配 a i6 j1 匹配 b i7 j2 匹配 a i8 j3 匹配 b i9 j4 匹配 c, 找到返回 9 - 5 1 即下标 5如果不放心还可以拿两个边界测一下模式串为空、模式串比主串还长。空串返回 0 是合理约定模式串更长的时候主循环最多扫一遍主串最后返回 -1不会数组越界。我在实际项目里习惯把 build_nextval 单独提出来因为同一个模式串会被多次用来匹配不同文本重复构建 nextval 纯属浪费。比如日志系统里每天要扫几百MB的文本但关键词是固定的几个这时候预构建一次 nextval匹配时时间复杂度才真正接近 O(m n)。4. 复杂度分析和实际性能表现4.1 为什么时间复杂度是O(mn)很多人只是把 O(mn) 当成结论背下来了却没理解为什么。KMP 的高明之处在于主串指针 i 永远不回头。你可以把 i 想象成一只只往前爬的蜗牛哪怕失配了也只是 j 跳回 nextval 指定的位置i 不动下一次比较还是从当前 i 继续。所以整个匹配过程i 最多移动 n 次j 的移动虽然看起来多但每次回退都指向一个更小的下标总体回退次数不会超过前移次数加常数整段匹配是线性的。build_nextval 同理i 和 j 也都不回头构建过程是 O(m)。两边叠加总复杂度 O(m n)。这里有一个很容易误解的点nextval 的回退跳来跳去为什么不算额外复杂度因为 j 每次回退之后下一次进入p[i] p[j]分支时j 都会增大也就是说每个位置最多被“成功推进”一次回退的总次数是有上限的。如果你做过 LeetCode 上的一些字符串匹配题比如反复需要 cut 掉特定子串或统计子串出现次数KMP 的这个线性特性会非常明显。暴力匹配在最坏情况下比如主串全是a、模式串是aaaab,每挪一个位置就要比 4 次复杂度直接 O(n*m)数据量一大肉眼可见地慢。4.2 实测下来的性能底线和适用边界我之前在某公司做一个日志关键词监控模块规则里有两百多个固定关键词每天要扫大约几百万行日志。一开始偷懒直接用 Python 的字符串in判断后来发现数据量上来之后 CPU 飙升于是换成了 KMP。换完之后单条日志的关键词匹配时间下降了近一个数量级。注意语言内置的in本身也做了很不错的优化但它是通用优化针对你这一批固定关键词的重复匹配场景KMP 预计算的收益就体现出来了。但我也要泼一盆冷水KMP 并不是万能的。如果你的模式串很短比如一两个字符那 KMP 的预计算开销反而是负优化直接用暴力或者内置函数更快。如果模式串集合很大且不固定比如搜索引擎的实时查询词那要选的数据结构是 Trie 或 AC 自动机KMP 在一个主串里匹配一个固定模式串的场景才是舒适区。还有一个工程细节在 Python 里如果你只是偶尔做一次pattern in text,内置的 CPython 底层算法很可能已经比手写 KMP 还快因为 C 语言级别的循环开销远小于 Python 字节码循环。KMP 真正的优势在于高重复调用、可预编译、跨语言一致性这三点的组合场景。5. 工程落地的几个真实场景5.1 日志系统里的敏感词过滤我最早在生产环境用 KMP就是做日志脱敏。日志里出现手机号、身份证号这类信息时会拿一批正则去匹配后来发现某条日志恰好在超大文本里反复命中同一类模式正则在长文本上的性能不够稳定于是改成先用 KMP 定位固定关键词再对命中位置做上下文裁剪。这样正则只需要在小片段上跑一次整体吞吐立刻上来了。这种场景的关键经验是把“定位”和“后处理”拆开。KMP 只负责告诉你“在哪命中”命中之后模板如何替换规则如何匹配都交给上一层逻辑。这样做的好处是模块边界清晰也不需要在 KMP 里塞很多业务判断出问题时很容易排查。5.2 编辑器里的查找与光标跳转做文本编辑器或者代码编辑器时CtrlF 的查找功能是最常见不过的需求。编辑器里的文本经常是 10 万行起步你在一个超大文件里搜一个关键字如果用暴力匹配最坏情况会卡顿。用 KMP 的话第一次搜索时构建一次 nextval后续一直用同一关键词继续搜索时可以直接复用体验上基本是秒出结果。我当时在一个简易代码编辑器里实现“查找下一个”功能做法是把搜索词对应的 nextval 缓存起来用户按 F3 往下找时直接从上次匹配位置继续而不是每次从头扫。这样只改了几十行代码性能提升却非常明显。你可能会说现代编辑器内置算法更复杂但作为学习项目或轻量内部工具KMP 这套思路完全够用。5.3 文本比对工具里“查找共同子串”的前置加速还有一类场景是两篇文章之间找相同片段。直接做差分或者最长公共子串复杂度都很高。常规思路是先把长文本切成小块再用 KMP 或其它匹配算法快速定位疑似相同片段最后在疑似片段上做精细比对。KMP 在这里扮演的是“粗筛”角色它不需要保证语义正确只需要保证不漏报。这种“粗筛 精细”的组合也更贴近真实工程思维不要指望一套算法解决所有问题。KMP 负责快后续的语义分析负责准二者配合才是完整方案。6. 踩坑记录与问题排查速查表6.1 我实际写过KMP后踩过的坑先说我个人栽得最狠的一个坑边界条件里的i m-1和j -1。写 build_nextval 的时候循环条件到底是i m还是i m - 1决定了最后一位的 nextval 是否正确。很多人照着网上的代码抄一跑测试用例发现返回的位置不对又debug半天最后发现是构建的时候越界访问了pattern[i]或pattern[j]。我的建议是构建 nextval 时循环到m-1为止因为我们需要为每个位置填值但最后一轮递推时i最多到m-2就可以把m-1位置的值填好再往后就没有意义了。第二个坑是主串或模式串长度为零。不少模板代码直接裸奔没判断空串结果要么返回奇怪下标要么直接越界。工程上一定要先做防御式判断模式串为空返回 0 或 -1 的语义要提前约定好主串为空而模式串非空返回 -1。这类 corner case 在笔试和线上排查都容易踩千万别觉得幼稚。第三个坑和 nextval 本身有关很多人从 next 改成 nextval 时只改了构建函数匹配时的失配回退还是写j next[j],导致优化没有生效。这种代码能跑通简单用例但性能测试一上就露馅。改的时候要检查两处构建时用nextval赋值匹配回退时也要用nextval。6.2 常见问题速查表症状可能原因处理办法匹配结果位置差一位下标约定不一致有的模板主串从1开始有的从0开始统一从0开始返回时明确是起始下标还是结束下标模式串超长时崩溃构建循环或匹配循环越界检查构建循环上界匹配循环要加i n和j m条件匹配结果漏掉重叠子串匹配成功后 j 直接从0重新开始需要统计重叠时匹配成功后设j nextval[j-1]或j nextval[j]按语义选择性能提升不明显模式串太短或调用次数太少KMP优势在高频重复匹配场景不对建议用内置函数nextval 一直算不对回退时没用 nextval 而是用了 next检查j nextval[j]分支是否漏改空串处理异常缺少防御式判断函数开头统一处理m 0、n 0的情况遇到问题的时候我自己的调试习惯是先写一个最小复现用例比如主串abababc模式串ababc在纸上推一遍结果再和代码输出对比。如果还查不出来就在 i、j 变化的关键位置加打印肉眼跟踪几轮。对于 KMP 这种纯逻辑算法用调试器反而不如打印来得直观因为状态转移就在两个分支里几行日志就能定位问题。最后分享一个我自己用得很顺手的经验把“构建 nextval”和“执行匹配”分层封装前者只依赖模式串后者只依赖主串和已构建的 nextval。这样单元测试只需要分别测两个函数的边界集成测试只测匹配结果是否符合预期。做工程项目的时候这种拆分也能让团队里其他人快速上手不用每次都从头捋 KMP 的推导过程。我后来再回头看自己第一次写 KMP 时留下的代码发现最值钱的不是算法本身那几十行而是在边界和优化上攒下来的这些细节。希望你也能少走一些我走过的弯路。