KMP算法详解：从next数组手推到代码实现，彻底搞懂字符串匹配

我在学习字符串匹配的时候第一次接触 KMP 算法说实话是有心理阴影的。网上帖子看了不少next 数组的计算方法五花八门有说从 1 开始的有说从 0 开始的还有说整体右移再补负一的同一段代码换个写法就看不懂了。后来自己踏踏实实推导了几十遍踩坑踩到怀疑人生才把这块骨头啃下来。这篇笔记就是我的完整复盘从暴力匹配为什么慢到 KMP 到底在优化什么再到 next 数组怎么算、代码怎么写全部按我自己最容易理解的方式整理一遍。适合刚接触字符串匹配、被教材里简略推导绕晕的人也适合面试前想快速把 KMP 原理和代码理顺的人。如果你只是想背模板这文章可能不够精简但如果你想真正搞懂它我把能踩的坑都替你踩完了。1. 为什么暴力匹配不够用1.1 暴力匹配的遍历方式字符串匹配解决的是一个问题在文本串 text 里找模式串 pattern返回 pattern 首次出现的位置。最直觉的做法就是双重循环外层指针 i 表示文本串的起始位置内层指针 j 和模式串逐字符比对一旦遇到不匹配i 回退到这次匹配的起始位置的下一位j 回到 0重新开始。举例来说text abcabcabdpattern abcabd。一开始 i0 和 j0 逐步比对前五个字符 a、b、c、a、b 都相同到第六个字符时 text[5] c 而 pattern[5] d不匹配。暴力匹配的做法是把 i 回退到 1、j 回退到 0重新从 text[1] b 和 pattern[0] a 开始比。这种回退是盲目的因为 text[1] 到 text[5] 这几个字符在上一轮比对中已经扫描过了但算法把它们全丢了。时间复杂度上最坏情况为 O(m×n)m 是文本串长度、n 是模式串长度。比如 text 全是 apattern 是 aab 时会反复比对到最后一位才失败每次都从下一位重新来。这种低效在文本长度为百万级、模式串长度又比较大时是不能忍的。1.2 KMP 的核心思想KMP 的高明之处在于不匹配发生时它不把已扫描过的 text 区域重新当作陌生字符处理而是利用模式串自身的结构信息让 i 保持不动只移动 j。实现这个效果的关键是把模式串的「部分匹配信息」预先计算出来。也就是说模式串里每个位置之前的部分它的前缀和后缀有多少位是相同的这个信息被记录在 next 数组中。匹配失败时j 可以直接跳到某个位置而不是回到 0因为前面的部分已经确定匹配上了。想理解 KMP先要理解一个转变匹配过程不再是「文本串指针移动」而是「模式串自己滑动」。文本串指针只增不减每次失配消耗的是模式串的已知信息而不是重新扫描文本。这是 KMP 时间复杂度能到 O(mn) 的根本原因。2. next 数组到底在算什么2.1 前缀和后缀的定义next 数组的计算方法是所有 KMP 学习者的第一道坎。我的经验是先把「前缀」「后缀」这两个词搞到滚瓜烂熟再说别的。对于一个字符串 s它的前缀是除去最后一个字符后从开头连续取出的若干字符组合后缀是除去第一个字符后从结尾连续取出的若干字符组合。空串和整个字符串不算在内因为它们一个太特殊、一个没有信息量。以 abab 为例它的真前缀有a、ab、aba真后缀有b、ab、bab。注意 abab 本身和空串都不计入候选。那么 abab 的最长相等前后缀长度就是 2因为 ab 既是前缀也是后缀同时它也是所有相等前后缀里最长的那一个。next 数组里存的本质上就是模式串每个前缀子串的「最长相等前后缀长度」。这个长度决定了失配时模式串该如何滑动。2.2 手动推导 next 数组这里我以 pattern ababcabaa 为例完整手推一遍。先约定 next[i] 表示 pattern[0..i] 这段子串中最长相等前后缀的长度。i0子串 a最长相等前后缀长度是 0。i1子串 ab前缀 a、后缀 b不相等next[1]0。i2子串 aba前缀 a、ab后缀 ba、a其中有 a 相符next[2]1。i3子串 abab前缀 a、ab、aba后缀 bab、ab、b最长相等的是 abnext[3]2。i4子串 ababc前缀 a、ab、aba、abab后缀 babc、abc、bc、c没有相符的next[4]0。i5子串 ababca前缀 a、ab、aba、abab、ababc后缀 babca、abca、bca、ca、a相等的最长是 anext[5]1。i6子串 ababcab前缀 a、ab、aba、abab、ababca、ababcab这个不取后缀 babcab、abcab、bcab、cab、ab、b最长相等的是 abnext[6]2。i7子串 ababcabaa 前面误写我们改成 ababcabaa 的第七位实际上 pattern ababcabaa 时i7 对应子串 ababcaba前缀里和最长后缀 abca? 不对我重新对齐一下。这里我想提醒一个自己踩过的坑手推的时候字符串千万别数错位。pattern ababcabaa我一位一位写清楚下标 i字符子串 pattern[0..i]最长相等前后缀长度0aa01bab02aaba13babab24cababc05aababca16bababcab27aababcaba38aababcabaa1i7 时子串是 ababcaba前缀 a、ab、aba、abab、ababc、ababca、ababcab后缀 babca? 我仔细检查子串 ababcaba 的真后缀是 b、ab、aba、caba、bcaba、abcaba、babcaba。最长相等的是 aba长度 3。所以 next[7]3。i8 时子串 ababcabaa真后缀有 a、aa、baa、abaa、cabaa、bcabaa、abcabaa、babcabaa和前缀能对上的最长是 a长度 1next[8]1。这个手动推导过程很笨但一定得练几次。你会发现 next 数组不是凭空生成的一组数字而是每个位置之前那段字符串的真实前缀后缀特征这对接下来的递推代码理解极有帮助。2.3 递推求解 next 的原理手推会了还要理解计算机是怎么高效算的。如果每个位置都从头比较前后缀复杂度就退化了。KMP 的经典做法是利用 next[i-1] 的结果来推导 next[i]这一步用到了递推的思想。假设我们已经知道 next[i-1] k说明 pattern[0..k-1] 和 pattern[i-k..i-1] 是相同的也就是说长度为 k 的前缀和长度为 k 的后缀对应相等。现在要看 i 位置加入新字符 pattern[i] 之后最长相等前后缀能有多长若 pattern[i] 等于 pattern[k]说明原来这对相等的 k 位前缀/后缀都能各自往后延一位于是 next[i] k1k 也同步加 1。若 pattern[i] 不等于 pattern[k]说明不能简单地延长。此时已知前缀串 pattern[0..k-1] 里仍然存在更短的相等前后缀这正是 next[k-1]我们把 k 回退到 next[k-1]然后再次比较 pattern[i] 和 pattern[k]如果还不行就继续回退直到 k0 或者匹配成功。你可能已经发现这个回退过程和匹配失败时的主循环是一模一样的。这就是 KMP 设计最精妙的地方计算 next 的过程本质上是让模式串自己和自己做匹配从而把模式串的每一个字符对应的回退信息都提前算好。用代码写出来就是vectorint getNext(const string p) { int n p.size(); vectorint next(n, 0); for (int i 1; i n; i) { int k next[i - 1]; while (k 0 p[i] ! p[k]) { k next[k - 1]; } if (p[i] p[k]) { k; } next[i] k; } return next; }这段代码里最容易被忽略的细节是next[k - 1] 只有在 k 0 时才合法所以 while 条件必须先判断 k 0。我第一次写的时候把条件顺序搞反了数组越界直接崩溃。3. 主循环和 next 数组的配合3.1 匹配主循环的写法算好 next 数组后主循环就顺理成章了。用两个指针i 遍历 textj 遍历 pattern。每轮循环做的事情是如果 text[i] 等于 pattern[j]i 和 j 都前进一位。如果不等且 j 0把 j 变为 next[j-1]i 不动。如果不等且 j 0说明模式串第一个字符都对不上i 前进一位。当 j 走完整个 pattern说明匹配成功返回 i - n 作为起始下标。如果 text 全部遍历完还没有匹配成功返回 -1。int kmpSearch(const string text, const string pattern) { int m text.size(), n pattern.size(); if (n 0) return 0; vectorint next getNext(pattern); int j 0; for (int i 0; i m; i) { while (j 0 text[i] ! pattern[j]) { j next[j - 1]; } if (text[i] pattern[j]) { j; } if (j n) { return i - n 1; } } return -1; }这里的主循环代码风格朴素但有个细节当 j 0 且 text[i] 不等于 pattern[0] 时while 不会执行if 判断也不满足i 自然前进。这个分支不需要额外写 else整洁又不容易出错。3.2 next 数组下标从 0 还是从 1 开始这是网上争论最多的问题之一也是新手最容易困惑的点。不同的教材和代码模板对 next 的定义不同常见的有三种next[i] 表示 pattern[0..i] 的最长相等前后缀长度我上面采用的就是这种。next[i] 表示 pattern[0..i-1] 的最长相等前后缀长度相当于把前一种定义整体右移一位。next[i] 表示前一种定义整体右移后第一个位置补 -1配合「失配时 j 跳到 next[j]」这种写法使用。这三种写法都能实现 KMP出错往往是因为混用。我自己的建议是认准一种定义把它对应的代码和推导全部统一。不要把两种模板拼在一起否则调试到天亮也别想跑对。我的模板选第一种因为它的 next 数组值和「该位置本身字符」无关只和它之前的部分有关手推时不容易错位主循环失配时用 j next[j-1] 回退逻辑上最贴近前缀后缀的原始定义。3.3 边界条件与空串问题KMP 的边界问题主要集中在这几个位置pattern 为空串时任何文本串都和它匹配返回 0 最合理。text 为空串而 pattern 非空直接返回 -1不需要走循环。两串等长且完全匹配时j 在最后一个字符处前进到 n返回 0 或 1 要看下标约定别搞混。匹配成功后如果想继续找下一个匹配位置可以让 j 回退到 next[j-1]而不是整轮重新开始。实际项目里建议把这些边界条件放在函数入口统一处理避免在主循环里堆一堆 if。代码的可读性会提升很多别人 review 的时候也更容易看懂。4. 实操中遇到的常见问题与排查技巧4.1 最常见的 next 数组越界问题我初学 KMP 时遇到最多的报错就是数组越界而且越界的位置非常隐蔽。典型场景是主循环里 j 0 时执行 j next[j-1]但 next 数组长度算错或者某个 next 值计算得过大导致回退后仍然访问越界。排查这种问题有一个很实用的办法单独写一个测试函数固定模式串打印完整的 next 数组手工验证每一个值。我列一个小工具函数方便自己在本地验证void debugNext(const string p) { vectorint next getNext(p); cout pattern: p endl; cout next: ; for (int x : next) cout x ; cout endl; }把刚学过的 ababcabaa 输进去输出应该是 0 0 1 2 0 1 2 3 1如果对不上就说明 getNext 里有问题一边打印一边人肉模拟一遍很快能定位。4.2 死循环问题与调试思路另一个高频问题是死循环。主要出现在主循环里 while 回退条件写得不对导致 j 回退到某一个值后永远无法前进i 也一直不增加。最常见的错误写法是把回退写成 j next[j]对应上面说的第三种 next 定义但你的 next 数组却按第一种定义生成于是两个约定错位回退逻辑陷入混乱。这种情况下的调试思路是在循环里打印 i、j、text[i]、pattern[j]、next[j] 这几个值观察 j 的回退路径。如果 j 在回退过程中回到了原值说明 next 的定义和回退公式不匹配。我踩过几次坑之后总结的经验是写 KMP 之前先想清楚一件事——「我这个 next 数组失配时 j 要跳到哪」。方案定了主循环和 getNext 函数必须配套重写。千万别套别的代码十有八九会翻车。4.3 匹配多个位置时的处理有时候不仅要找第一个匹配位置还要找所有匹配位置。比如文本串里出现多段模式串需要统计出现次数或打印下标。处理方式有两种第一种是在主循环里匹配成功之后把 i i - n 1 记录下来然后让 j next[j-1] 继续走不要 break。这里用到的 next[j-1] 恰好是模式串自身的部分匹配信息能保证不会漏掉重叠匹配。第二种是找到一次匹配后直接从 i - n 2 开始重新跑一遍 KMP这样简单但效率略差。个人建议用第一种因为正好能体现 KMP 的优势匹配失败和匹配成功之后接着找本质上是同一件事都靠 next 数组避免重复扫描。4.4 面试和考试时的速查技巧如果你是为了准备面试或者应付算法考试我推荐一个快速手推 next 数组的方法先把模式串位置编号然后对每个位置 i只看 pattern[0..i-1] 这段前缀从后往前数最长相等前后缀长度。这样比从 i 位置直接数要少犯一个边界错误因为不需要考虑当前位置的字符规则更单一。再给一个实战技巧笔试题里如果只要求写核心代码可以直接把 next 数组的递推写成循环不要在里面混入分支过多的高级技巧。简单朴素的写法不容易错阅卷人也一眼能看懂。5. KMP 的变体与扩展思考5.1 从 next 到 nextvalnext 数组还有一个常见变体叫 nextval它的作用是进一步压缩回退路径。原理是当主循环里 text[i] 不等于 pattern[j] 时j 回退到 next[j-1]但这个新的位置上的字符如果和原来的 pattern[j] 相同那么这次回退其实仍然会匹配失败于是可以继续回退跳过量到最短路径。nextval 的构建规则是在计算出 next[i] 后如果 pattern[i] 等于 pattern[next[i]]就令 nextval[i] nextval[next[i]]否则令 nextval[i] next[i]。这个优化对某些重复字符很多的模式串特别有效能把最坏情况下的回退次数再压低一些。实际编码时nextval 可以让主循环里 while 的迭代次数显著减少但代价是 getNext 的代码稍复杂一点。如果模式串较短差别不大如果模式串非常长且包含大量重复片段nextval 就值得用了。5.2 KMP 和 Boyer-Moore、Sunday 的对比学到一定阶段你会发现 KMP 不是唯一的字符串匹配算法。Boyer-Moore 从模式串尾部开始匹配利用坏字符规则和好后缀规则跳过大量位置对英文文本这类自然语言通常效率更高Sunday 算法更简单粗暴直接用文本串下一个参与匹配的字符来决定模式串的跳跃距离工程上很受欢迎。但这些算法各有各的适用范围。KMP 最厉害的地方是保证最坏情况下也是线性时间不像某些算法平均快但最坏场景退化成 O(m×n)。如果你需要一种稳定、可证明、模式串字符集比较固定、又不太依赖具体文本分布的算法KMP 依然是最稳妥的选择。学完 KMP 再去看其他匹配算法会更容易理解它们各自解决的问题和取舍原因所以我的建议是别只背模板先把 KMP 吃透它的前缀函数思想在字符串处理里的用处远不止匹配本身AC 自动机、字符串哈希、循环节判定这些后续内容都离不开它。6. 手写实现时的一些心得6.1 避免过度优化导致看不懂我见过不少同学学完 KMP 后喜欢把它写得很花哨一行代码解决很多事看起来很厉害但之后自己看都费劲。我个人的看法是重点是性能和逻辑正确而不是代码短。下面这个版本是我放在自己代码库里最常拿出来用的兼顾清晰和性能vectorint prefixFunction(const string p) { int n p.size(); vectorint pi(n, 0); for (int i 1; i n; i) { int j pi[i - 1]; while (j 0 p[i] ! p[j]) { j pi[j - 1]; } if (p[i] p[j]) { j; } pi[i] j; } return pi; } int strStr(string text, string pattern) { int m text.size(), n pattern.size(); if (n 0) return 0; vectorint pi prefixFunction(pattern); int j 0; for (int i 0; i m; i) { while (j 0 text[i] ! pattern[j]) { j pi[j - 1]; } if (text[i] pattern[j]) { j; } if (j n) { return i - n 1; } } return -1; }这段代码里没有用到任何花哨的技巧但读者只要理解前缀和后缀的定义就能一步步跟着推下来。6.2 测试用例的选取思路写完 KMP 之后不能只跑一个 hello world。我建议至少准备下面几类测试用例模式串就是单个字符且出现在文本串开头中间结尾各一次。模式串全部由同一个字符组成比如 aaaa文本串也全是 a。模式串含大量重复前缀比如 aabaabaaa。模式串比文本串还长此时必须返回 -1。模式串不存在于文本串但前缀和后缀高度重合。匹配结果有重叠比如 text abababapattern aba期望匹配位置为 0、2、4。这些用例能覆盖绝大多数边界情况。每改一次代码都把这套用例重新跑一遍比写一屏测试代码来得实在。6.3 关于空间复杂度KMP 需要一个 n 长度的 next 数组空间复杂度 O(n)。如果你处理的数据很大可以考虑在模式串很短时直接用简单的暴力匹配能省下 next 数组的构建时间。不过大多数场景下KMP 的稳定性更重要。我个人在实际工程里很少碰到比 KMP 更合适的字符串匹配需求因为文本搜索库通常已经封装好了但在面试手撕代码、算法竞赛和写底层字符串工具的时候KMP 依然是无法绕开的基本功。7. 总结我自己的一点点经验KMP 算法最让我感慨的地方在于它的核心并不复杂但无论是手推 next 数组还是把 next 数组和主循环关联起来都对严谨性提出了很高要求。我学这段内容的时候反复犯过同一个错总想跳步总觉得自己懂了原理就可以直接写代码结果每次一到j next[j-1]这一步就开始怀疑人生。后来我把心态放平坚持每次都用笔在纸上推一个完整例子把 i、j、text 下标、pattern 下标和 next 数组全部标出来一步一步走完整个匹配过程才算真正建立了直觉。现在如果你问我 KMP 是什么我会说它就是用模式串自己的部分匹配信息来决定失配时模式串该往右移动多远避免文本串指针回退。最后再分享一个小技巧如果实在记不住 next 的递推写法可以退一步先用双重循环计算每一个位置的「最长相等前后缀长度」这样性能虽然退化但逻辑绝对正确再在它的基础上做优化推导不容易把自己绕进去。KMP 不是玄学它是可以用笨方法验证、再逐步精进的算法理解了这一层后面学 Z 函数、Manacher、AC 自动机都会轻松很多。