写 KMP 算法这篇文章其实是我早就想做的事。字符串匹配是写代码几乎绕不开的一件事不管你是刷 LeetCode、打信奥、做文本处理还是写搜索引擎、做日志分析KMPKnuth-Morris-Pratt算法都是绕不过去的一道坎。很多人第一次接触它的时候会被那个不叫 next 就是叫 pi 的数组搞晕也可能背下了代码却说不清为什么 j next[j] 这行代码的灵魂作用。这篇文章我尽量用大白话加手把手推导的方式把你从暴力匹配一路带到 KMP 的完整实现包括 next 数组的手算套路、代码怎么写、边界怎么卡、以及实际工程里常见的坑。不论你是刚学数据结构与算法的学生还是准备面试的开发者我建议你耐着性子把 next 数组的推导过程亲手走一遍比背十遍代码都管用。1. 从暴力匹配说起KMP 到底解决了什么问题1.1 暴力匹配的痛点先聊个最朴素的场景。给你一个长字符串叫主串习惯上用 T 表示和一个短字符串叫模式串用 P 表示让你找出 P 在 T 中第一次出现的位置。大多数人脑袋里第一个蹦出来的办法就是暴力匹配从 T 的每一个位置开始逐个字符去和 P 比一旦中间某个字符不一致就放弃当前这个位置把起点往后挪一位重新从 P 的第一个字符开始比。这个办法的代码非常简单写出来也就十行左右int bruteForce(const string text, const string pattern) { int n text.length(), m pattern.length(); for (int i 0; i n - m; i) { int j 0; while (j m text[i j] pattern[j]) j; if (j m) return i; } return -1; }看起来没什么问题但它在最坏情况下的时间复杂度是 O(n×m)。什么时候会踩到这个最坏情况我给你举个例子主串是AAAAAAAAAAAAAAAAAB模式串是AAAAB。每次你都要把模式串前四个A全部比完到第五个字符才失败然后起点挪一位再把四个A比一遍。这种重复劳动在 n 和 m 都很大的时候会直接把程序拖垮。暴力匹配浪费在哪浪费在它把已经比对过的、明明可以用的信息直接扔掉了。你在一段文本的某个位置已经成功匹配了前 k 个字符说明你对这段文本的内容已经有一定的“了解”但暴力匹配对你的了解毫不领情重新从零开始。KMP 算法的价值就是把这些已经获取到的信息利用起来不回头、不浪费。1.2 KMP 的核心思想少走回头路KMP 是三位计算机科学家 Knuth、Morris、Pratt 在 1977 年发表的经典算法。它最核心的思想可以概括成一句话当匹配失败时主串的指针不回溯或者说不回退只移动模式串把模式串“滑动”到一个让已经匹配的前缀信息得到最大利用的位置。所谓“主串指针不回溯”意思是我在匹配的过程中主串永远只往前走绝对不会因为匹配失败而退回去重新比较。这个特性在文本非常长、只能流式读入的场景下特别有用因为你不需要把文本缓存下来反复扫描。那模式串到底滑多远这就引出了整个算法的灵魂——next 数组。next 数组的作用是在我们匹配到模式串第 j 个位置失败的时候告诉我们应该从模式串的哪个位置继续跟主串的当前位置比较。回答这个问题的关键是搞清楚模式串自身的结构模式串已经成功匹配的那一段前缀里后缀能跟前缀重叠多少。我打个比方。你拿着一把尺子去量一段墙面量到某一段发现刻度和墙上的标记对不上了。你不会把尺子完全收回起点重新量而是会看看尺子上已经量过的那一截最后面几个刻度是不是跟最前面几个刻度长得一样。如果一样你可以把尺子往后挪让这一截重复的刻度直接对上已经量好的墙面接着往下量。KMP 干的就是这件事而 next 数组就是帮你决定尺子挪到哪个位置的那张对照表。2. next 数组整个算法的灵魂2.1 next 数组到底在求什么next 数组的定义网上的版本五花八门有的叫前缀函数prefix function有的直接就叫失败函数failure function。我先把最标准的定义写清楚后面所有推导都基于这个定义。对于模式串 Pnext[i] 表示的是P[0..i] 这个子串即从开头到第 i 个字符中最长的“相等前后缀”的长度。所谓前缀就是从一个字符串的开头截出来的子串所谓后缀就是从它的末尾截出来的子串。并且前缀和后缀都不能等于这个子串本身。举例来说对于字符串ABAB它的前缀有A、AB、ABA后缀有B、AB、BAB相等且长度不为 0 的只有AB所以最长相等前后缀长度是 2。为什么这个数有用回到匹配场景。假设我们匹配到模式串第 j 位的时候失败说明 P[0..j-1] 这 j 个字符已经全部和主串对应位置匹配成功了。如果 P[0..j-1] 存在一个长度为 k 的相等前后缀那就意味着主串中刚才已经匹配过的这段文本的末尾 k 个字符和模式串开头的 k 个字符是一样的。这时候我就不用把模式串移回起点而可以直接把模式串的第 k 位拿来跟主串的当前位置继续比——前面的 k 位已经天然对齐了。所以 next 数组里面的值就是用来告诉你在失配时把模式串的指针“回退”到哪个位置。注意这个“回退”是在模式串上回退主串的位置纹丝不动。2.2 手把手推导 next 数组很多教程喜欢直接给你一段求 next 数组的代码然后让你背下来。我建议你千万别这么干不理解推导过程的话代码改一个下标你马上就会懵。我们先拿一个具体模式串来走一遍比如ABABABC。第一步初始化。next[0] 0因为只有一个字符的子串没有真前后缀长度为 0。然后我们用一个指针 i 指向当前要计算的字符位置用另一个变量 j 来维护“当前已经匹配出的最长相等前后缀长度”。计算过程中j 实际上是一直在充当“已经匹配的前缀的长度”的角色。具体的计算规则是这样的我们从 i1 一直算到 i6每一次都尝试把 P[i] 和 P[j] 比较如果相等太好了说明最长相等前后缀的长度可以扩展一位所以 next[i] j 1j 也跟着加一然后 i 继续往后走。如果不相等就需要让 j 回退到 next[j-1]再重新比较直到 j0 或者遇到相等的情况。如果 j 已经退到 0 还是比不成那 next[i] 0。我们实际操作一下。i1j0比较 P[1]B 和 P[0]A不相等j 已经为 0所以 next[1]0。AB确实没有相等前后缀。i2j0比较 P[2]A 和 P[0]A相等所以 next[2]j11同时 j 变成 1。你检查一下ABA前缀A和后缀A确实相等长度是 1。i3j1比较 P[3]B 和 P[1]B相等next[3]j12j 变成 2。ABAB的最长相等前后缀是AB长度 2没问题。i4j2比较 P[4]A 和 P[2]A相等next[4]j13j 变成 3。ABABA的最长相等前后缀是ABA长度 3没问题。i5j3比较 P[5]B 和 P[3]B相等next[5]j14j 变成 4。ABABAB的最长相等前后缀是ABAB长度 4。i6j4比较 P[6]C 和 P[4]A不相等。这时候进入回退逻辑j 回退到 next[3]2再比较 P[6]C 和 P[2]A还是不相等继续回退j 回退到 next[1]0比较 P[6]C 和 P[0]A还不相等j 已经到 0无法再退所以 next[6]0。最终得到的 next 数组是[0, 0, 1, 2, 3, 4, 0]。每次 j 需要回退的时候你可能会问为什么是回退到 next[j-1]而不是 j-1 或者其他位置核心原因是P[0..j-1] 这段前缀内部可能也存在相等前后缀直接回退到 next[j-1] 能保证我还保留着模式串自身的部分匹配信息。这本质上是一个重叠子问题的递归计算也是 KMP 巧妙的地方。2.3 代码实现与边界处理理解了推导过程写代码就不难了。下面是 C 的实现vectorint buildNext(const string pattern) { int m pattern.length(); vectorint next(m, 0); int j 0; for (int i 1; i m; i) { while (j 0 pattern[i] ! pattern[j]) { j next[j - 1]; } if (pattern[i] pattern[j]) { j; } next[i] j; } return next; }注意几个关键细节j 表示的是到当前为止已匹配的前缀长度同时也是下一个要匹配的前缀字符下标。while 循环是 j 回退的核心。如果匹配不成功j 按 next[j-1] 回退而且这个过程可能发生多次。代码里没有特判 j0 的情况它自然地包含在 while 条件里当 j0 时while 条件不成立直接走后续的 if 判断。这个写法是最经典的 next 数组求法我建议你在自己的机器上一个字符一个字符地走一遍循环搞清楚每次 j 的变化。3. 匹配阶段的完整流程与复杂度分析3.1 匹配阶段如何配合 next 数组next 数组构建完成之后匹配阶段反而简单了。同样维护两个指针i 指向主串j 指向模式串规则如下逐个比较 T[i] 和 P[j]如果相等两者都往后走如果不等j 回退到 next[j-1]如果 j0而 i 不动如果 j 已经等于 0 且仍然不等说明模式串的第一位就对不上直接让 i 往后走一位。我写一个完整的匹配函数int kmpSearch(const string text, const string pattern) { int n text.length(), m pattern.length(); if (m 0) return 0; vectorint next buildNext(pattern); int j 0; for (int i 0; i n; i) { while (j 0 text[i] ! pattern[j]) { j next[j - 1]; } if (text[i] pattern[j]) { j; } if (j m) { return i - m 1; // 找到完全匹配返回起始下标 } } return -1; }这里有一个地方特别容易搞混构建 next 数组时我们处理的是模式串自身而匹配时我们处理的是主串和模式串之间的事。两者虽然都有 while 回退逻辑但语义完全不同。构建 next 数组的回退是在利用模式串的自我重叠信息匹配时的回退是在利用已经匹配成功的那一段模式串前缀的信息。你看代码长得像本质不同。我来模拟一个完整的匹配过程。主串 T ABABABCABABABC模式串 P ABABABC。用刚才求好的 next 数组[0, 0, 1, 2, 3, 4, 0]。一开始i0j0T[0]A 等于 P[0]Ai 和 j 都加一T[1]B 等于 P[1]BT[2]A 等于 P[2]AT[3]B 等于 P[3]BT[4]A 等于 P[4]AT[5]B 等于 P[5]BT[6]C 等于 P[6]C七位全部匹配成功j 变成 7等于 m返回 i - m 1 6 - 7 1 0。模式串从主串下标 0 开始完全匹配。假设换一种情况主串 T ABABABABC模式串仍然是ABABABC。i 走到 6 的时候T[6]AP[6]C不相等此时 j6所以 j 回退到 next[5]4i 保持不变。然后比较 T[6]A 和 P[4]A相等i 和 j 都加一接着 T[7]B 等于 P[5]B继续T[8]C 等于 P[6]C匹配成功返回 2。整个过程 i 只往前走完全没有回头。3.2 复杂度分析为什么 O(nm)KMP 的复杂度分析是面试高频问题我来给你一个直观的理解。构建 next 数组的循环里i 从 1 到 m-1 每次加一一共是 m-1 次j 只增不减但它在 while 循环里会不断回退。j 总共增加了多少次最多 m 次。因为每次 for 循环里 j 最多加一次一而 while 里的回退本质上是把之前加上的 j 值消耗掉所以整个过程中 j 的所有变化加起来不超过 2m 次。这是摊还分析的经典思想通俗地讲就是j 的“存款”总量有限回退只是把存款花掉总的花销不可能超过存款。因此构建 next 数组的复杂度是 O(m)。匹配阶段同理。i 从 0 到 n-1 总共走 n 次j 的每次增加都对应一次 i 的后移j 的值在所有循环里变化的总次数也不超过 2n所以匹配复杂度是 O(n)。总体时间复杂度 O(nm)空间复杂度 O(m)因为只需要存模式串的 next 数组。跟暴力匹配 O(n×m) 相比优势一目了然。不过我要补一句KMP 的常数因子不算小在普通的随机文本场景下暴力匹配的表现未必比 KMP 差甚至可能更快。KMP 真正的价值体现在最坏情况有保证的基础上——无论输入数据长什么样它都能保证在 O(nm) 时间内完成。这正是竞赛选手和底层库作者特别看重它的一点最坏情况足够可控。4. 常见问题与实战排查4.1 边界错位next 数组下标从 0 还是从 1 开始网上关于 next 数组的代码版本很多最大的分歧点在于“下标是从 0 开始还是从 1 开始”“next[i] 存的是最长相等前后缀长度还是这个长度减一”以及“失配时到底回退到 next[j] 还是 next[j-1]”。很多人学的时候被这些版本绕晕其实就是没搞清楚自己代码里 next 数组的定义。我上面给的实现采用的是最主流的做法模式串下标从 0 开始next[i] 表示 P[0..i] 的最长相等前后缀长度匹配失败时回退到 next[j-1]。这个版本写起来简单不容易出边界问题。但也有教材用另一种版本next[0] -1然后 next[i] 表示“失配时模式串指针跳转到的位置”。这两种本质上是一样的只是把回退逻辑前置到了数组里。你只要选定一种全程贯彻就不容易出错。最怕的是看代码时一会儿用这个版本一会儿用那个版本结果把自己绕进去。我的建议是考试或面试前把你常用的那版代码反复写熟日常多刷题巩固别零散地收集各种版本。4.2 nextval 优化避免连续失配的浪费KMP 有一个常见优化叫 nextval也叫优化后的 next 数组。它解决什么问题呢假设模式串是AAAAAB它的 next 数组是[0, 1, 2, 3, 4, 0]。如果在匹配到 P[4]A 时失配j 会退到 next[3]3可 P[3] 也是 A跟刚才失配的那个字符一模一样拿它再去跟主串比较必然还是失败。然后下一步 j 退到 next[2]2P[2] 还是 A又失败。这样连续跳好几次都是做无用功。nextval 的思路是如果回退后的字符 P[next[j-1]] 跟原字符 P[j] 相同那么这次回退实际上是无效的要继续回退。代码实现也很简单在构建 next 数组时多加一个判断if (pattern[i] pattern[j]) { j; // 优化如果新的 P[j] 等于 P[i]直接继承前面的 next 值 next[i] (pattern[i] pattern[j]) ? next[j - 1] : j; } else { // ... }准确讲nextval 优化的写法在不同版本里略有差异核心思路就是在求 next[i] 之后再额外检查 P[next[i]]或者说回退目标位置的字符是否等于 P[i]。如果相等说明回退后还是要比较同一个字符那就赋值为 next[next[i]]直接跳过这一步。注意nextval 优化的价值在模式串中重复字符很多的时候非常明显。但在字符重复率不高的模式串里优化效果不明显甚至因为多了一层判断而稍微慢一点。工程上如果你处理的数据没有明显的重复模式用普通 next 就够了如果你知道自己会在类似AAAAAB这样的模式串上反复匹配那 nextval 更稳。4.3 面试和竞赛中 KMP 的常见变形KMP 算法本身是一块敲门砖真正见功夫的是它的各种变形和应用。面试和竞赛里经常出现这么几类第一类是计数问题。要求统计模式串在主串中出现的次数这很容易匹配成功一个之后不要急着返回而是记录一次位置然后让 j 回退到 next[m-1]继续匹配。这样不会漏掉重叠出现的模式串比如主串AAAAA、模式串AA正常计数结果是 4 次。第二类是求最长重复子串或者最长公共前后缀问题。KMP 的 next 数组本身就是一组“最长相等前后缀”的信息所以很多字符串题目最终都能转化成对 next 数组的考察。比如求一个字符串的最长前后缀使得这个前后缀在字符串中间也出现过这类题往往需要对 next 数组做多次跳转分析。第三类是多模式串匹配。如果同时要匹配很多模式串KMP 就不够用了这时候要用 AC 自动机它本质上是在 Trie 树上做类似 KMP 的失败指针fail 指针跳转。理解了 KMP 的失配跳转思想再去看 AC 自动机会觉得非常顺畅。也就是说KMP 是你进入更高级字符串算法领域的地基。第四类是结合动态规划。有些字符串 DP 问题比如求“不包含某个子串的字符串个数”可以把 KMP 的 next 数组状态嵌入 DP 转移过程用来维护当前匹配到模式串的哪个位置。这种题比较硬核但理解了 KMP 状态转移的语义之后反而会觉得设计得很精巧。4.4 我的几个实操心得最后分享几个我在实际写代码和刷题中踩过的坑希望你不用再踩一遍。第一写代码的时候务必先处理模式串为空的情况。很多实现漏了if (pattern.empty()) return 0;这句话结果在输入空字符串时直接访问 next[-1] 或者越界程序崩溃。这种边界情况在面试现场很容易被忽略建议提前形成条件反射。第二调试 KMP 时别盯着代码空想。最好的方式是输出中间变量把 next 数组打印出来再手写模拟一遍匹配过程对着看。很多问题其实只是 next 数组算错了一位根本不涉及算法理解问题。打印中间变量这个习惯在调试所有复杂算法时都好使。第三如果你在竞赛中用 KMP 处理很大规模的数据注意用快读快写。KMP 本身虽然快但如果输入输出占了大量时间整体性能照样难看。IO 优化和算法优化是两回事但在实际工程里它们会一起决定最终效果。第四KMP 的很多变体比如 Z 算法、扩展 KMP和它求解的信息是相通的。Z 算法求的是每个位置 i 从 i 开头的子串和整个字符串的最长公共前缀长度跟 next 数组求的信息有微妙区别但代码形态非常相似。学有余力的话把 Z 算法和扩展 KMP 一起掌握了你对字符串前缀匹配这类问题的理解会一下子立体起来。我个人在实际使用中最深的感受是KMP 不是一个你背会了就完事的算法而是一种思维范式。它随时随地提醒我在处理有结构的、可重复的数据时先提取结构信息再进行配对远比你一张白纸一样从头开始试探高效得多。这个思路不仅在字符串匹配里有用在写解析器、处理编译器的词法分析问题、甚至在设计缓存淘汰策略的时候都隐隐约约有它的影子。希望你能把 next 数组的推导亲手练到滚瓜烂熟然后在一道道题目里慢慢体会它的妙处。
