1. 这一篇到底要解决什么问题

距离上一篇聊 KMP 基础已经有一阵子了。上一篇推完了 next 数组的手工推导，也用一个简单的文本匹配把流程跑通了，当时不少读者留言说“原理明白了，一写代码就废”，还有人说“感觉自己会了，但是换个模式串又算不对 next 数组”。这篇就是冲着这些问题来的。

KMP,全称是 Knuth-Morris-Pratt 字符串匹配算法，说实话它不是一个“用了就性能翻倍”的银弹，但是它在处理“一个主串里反复查同一个模式串”“大量文本里找一个固定关键词”这类场景时，效率确实碾压暴力匹配。我算是从学生时代就开始折腾这套算法，后来在某公司的日志检索模块里真正把 KMP 用到了生产环境，期间踩了不少坑，也总结了一套相对稳的写法和排查套路，这里分享出来，希望能帮卡在“看懂”和“写对”之间的同学跨过这个坎。

这篇的重点放在三块：一是把 next 数组升级为 nextval 的来龙去脉讲透，二是给出能直接抄的工程级实现，三是从复杂度、实际性能和常见错误三个角度帮你彻底“排雷”。如果你已经能把 next 数组从纸上推出来，但对代码实现和极端情况还没把握，这篇就是你的菜。如果你连 next 数组都没搞明白，建议先花半小时回顾上一篇，不然这篇读起来会有点费劲。

2. next数组到nextval：KMP优化中最容易翻车的一段

2.1 为什么朴素的next数组还不够

很多人在实现了第一版 KMP 之后，拿一个复杂的模式串一测就露馅了。比如模式串是aaaaab，用原始 next 数组去匹配主串aaaaacaaaaab，你会发现虽然整体复杂度还是线性的，但中间出现了不少“虽然知道该右移，但明明可以跳更多”的冗余移动。

这里的根子在于：next 数组本身记录的是“最长相同前后缀的长度”，但它没考虑一个更关键的问题，也就是当失配发生时，j回溯到next[j]之后，这个位置上的字符会不会依然是导致失配的那个字符。换句话说，如果模式串里有大量重复字符，你按 next 回退一次之后，很可能还是和主串失配的那个字符对比，那这次比较就是必然失败的。

举个例子，模式串aaaaab，假设某个时刻在j=4的位置失配，主串当前字符是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]，那就按经典思路回退 j，j = nextval[j]，直到j == -1或p[i] == p[j]为止。很多初学同学在这里犯迷糊的是：为啥回退的时候也用 nextval，而不用 next？我个人的理解是，回退的目标本来就是找一个“不会做无用功”的位置，既然 nextval 已经帮你把同字符跳过的问题过滤掉了，那回退用 nextval 自然比用 next 更彻底。

拿一个具体例子走一遍。模式串ababc，手工推导：

p: a b a b c i=0: nextval[0] = -1 i=1: j=0, p[1]=b != p[0]=a, 且 j==0, nextval[1] = 0 i=2: 回溯 j 时发现 p[2]=a, 可参考的前后缀拿 j=0 比较, p[2]==p[0], next[2]=1, 再检查 p[next[2]] p[1] = b != a, 所以 nextval[2] = 1 i=3: j=1, p[3]=b == p[1]=b, next[3]=2, 检查 p[next[3]] p[2]=a, 和当前 p[3]=b 不同, nextval[3]=2 i=4: j=2, p[4]=c != p[2]=a, 回退 j=nextval[2]=1, p[4]=c != p[1]=b, 回退 j=nextval[1]=0, p[4]=c != p[0]=a, j==-1, next[4]=0, nextval[4]=0

走到这里你就能感觉到，手工推 nextval 比推 next 多了一个“再判断一步”的动作，而这个动作正是减少无用比较的关键。我建议学的时候别直接背代码，拿三四个模式串手工推一遍，推完再用代码验证，印象会深刻很多。

3. 完整实现：从暴力到KMP再到优化KMP

3.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匹配模式串ababc：

build_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 i=0 j=0 匹配 a i=1 j=1 匹配 b i=2 j=2 匹配 a i=3 j=3 匹配 b i=4 j=4 失配, 主串是 a, 模式是 c, j=nextval[4]=0 i=4 j=0 匹配 a i=5 j=1 主串 a 模式 b 失配, j=nextval[1]=0 i=5 j=0 匹配 a i=6 j=1 匹配 b i=7 j=2 匹配 a i=8 j=3 匹配 b i=9 j=4 匹配 c, 找到，返回 9 - 5 + 1 即下标 5

如果不放心，还可以拿两个边界测一下：模式串为空、模式串比主串还长。空串返回 0 是合理约定；模式串更长的时候，主循环最多扫一遍主串，最后返回 -1，不会数组越界。

我在实际项目里习惯把 build_nextval 单独提出来，因为同一个模式串会被多次用来匹配不同文本，重复构建 nextval 纯属浪费。比如日志系统里每天要扫几百MB的文本，但关键词是固定的几个，这时候预构建一次 nextval，匹配时时间复杂度才真正接近 O(m + n)。

4. 复杂度分析和实际性能表现

4.1 为什么时间复杂度是O(m+n)

很多人只是把 O(m+n) 当成结论背下来了，却没理解为什么。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 编辑器里的查找与光标跳转

做文本编辑器或者代码编辑器时，Ctrl+F 的查找功能是最常见不过的需求。编辑器里的文本经常是 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 常见问题速查表

遇到问题的时候，我自己的调试习惯是先写一个最小复现用例，比如主串abababc模式串ababc，在纸上推一遍结果，再和代码输出对比。如果还查不出来，就在 i、j 变化的关键位置加打印，肉眼跟踪几轮。对于 KMP 这种纯逻辑算法，用调试器反而不如打印来得直观，因为状态转移就在两个分支里，几行日志就能定位问题。

最后分享一个我自己用得很顺手的经验：把“构建 nextval”和“执行匹配”分层封装，前者只依赖模式串，后者只依赖主串和已构建的 nextval。这样单元测试只需要分别测两个函数的边界，集成测试只测匹配结果是否符合预期。做工程项目的时候，这种拆分也能让团队里其他人快速上手，不用每次都从头捋 KMP 的推导过程。

我后来再回头看自己第一次写 KMP 时留下的代码，发现最值钱的不是算法本身那几十行，而是在边界和优化上攒下来的这些细节。希望你也能少走一些我走过的弯路。