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

我在学习字符串匹配的时候，第一次接触 KMP 算法，说实话是有心理阴影的。网上帖子看了不少，next 数组的计算方法五花八门，有说从 1 开始的，有说从 0 开始的，还有说整体右移再补负一的，同一段代码换个写法就看不懂了。后来自己踏踏实实推导了几十遍，踩坑踩到怀疑人生，才把这块骨头啃下来。

这篇笔记就是我的完整复盘，从暴力匹配为什么慢，到 KMP 到底在优化什么，再到 next 数组怎么算、代码怎么写，全部按我自己最容易理解的方式整理一遍。适合刚接触字符串匹配、被教材里简略推导绕晕的人，也适合面试前想快速把 KMP 原理和代码理顺的人。如果你只是想背模板，这文章可能不够精简；但如果你想真正搞懂它，我把能踩的坑都替你踩完了。

1. 为什么暴力匹配不够用

1.1 暴力匹配的遍历方式

字符串匹配解决的是一个问题：在文本串 text 里找模式串 pattern，返回 pattern 首次出现的位置。最直觉的做法就是双重循环，外层指针 i 表示文本串的起始位置，内层指针 j 和模式串逐字符比对，一旦遇到不匹配，i 回退到这次匹配的起始位置的下一位，j 回到 0，重新开始。

举例来说，text = "abcabcabd"，pattern = "abcabd"。一开始 i=0 和 j=0 逐步比对，前五个字符 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 全是 'a'，pattern 是 "aab" 时会反复比对到最后一位才失败，每次都从下一位重新来。这种低效在文本长度为百万级、模式串长度又比较大时是不能忍的。

1.2 KMP 的核心思想

KMP 的高明之处在于：不匹配发生时，它不把已扫描过的 text 区域重新当作陌生字符处理，而是利用模式串自身的结构信息，让 i 保持不动，只移动 j。

实现这个效果的关键，是把模式串的「部分匹配信息」预先计算出来。也就是说，模式串里每个位置之前的部分，它的前缀和后缀有多少位是相同的，这个信息被记录在 next 数组中。匹配失败时，j 可以直接跳到某个位置，而不是回到 0，因为前面的部分已经确定匹配上了。

想理解 KMP，先要理解一个转变：匹配过程不再是「文本串指针移动」，而是「模式串自己滑动」。文本串指针只增不减，每次失配消耗的是模式串的已知信息，而不是重新扫描文本。这是 KMP 时间复杂度能到 O(m+n) 的根本原因。

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] 这段子串中，最长相等前后缀的长度。

• i=0，子串 "a"，最长相等前后缀长度是 0。
• i=1，子串 "ab"，前缀 a、后缀 b，不相等，next[1]=0。
• i=2，子串 "aba"，前缀 a、ab，后缀 ba、a，其中有 "a" 相符，next[2]=1。
• i=3，子串 "abab"，前缀 a、ab、aba，后缀 bab、ab、b，最长相等的是 "ab"，next[3]=2。
• i=4，子串 "ababc"，前缀 a、ab、aba、abab，后缀 babc、abc、bc、c，没有相符的，next[4]=0。
• i=5，子串 "ababca"，前缀 a、ab、aba、abab、ababc，后缀 babca、abca、bca、ca、a，相等的最长是 "a"，next[5]=1。
• i=6，子串 "ababcab"，前缀 a、ab、aba、abab、ababca、ababcab（这个不取），后缀 babcab、abcab、bcab、cab、ab、b，最长相等的是 "ab"，next[6]=2。
• i=7，子串 "ababcabaa" 前面误写，我们改成 "ababcabaa" 的第七位，实际上 pattern = "ababcabaa" 时，i=7 对应子串 "ababcaba"，前缀里和最长后缀 "abca"? 不对，我重新对齐一下。

这里我想提醒一个自己踩过的坑：手推的时候字符串千万别数错位。pattern = "ababcabaa"，我一位一位写清楚：

i=7 时子串是 "ababcaba"，前缀 a、ab、aba、abab、ababc、ababca、ababcab，后缀 babca? 我仔细检查：子串 ababcaba 的真后缀是 b、ab、aba、caba、bcaba、abcaba、babcaba。最长相等的是 "aba"，长度 3。所以 next[7]=3。i=8 时子串 "ababcabaa"，真后缀有 a、aa、baa、abaa、cabaa、bcabaa、abcabaa、babcabaa，和前缀能对上的最长是 "a"，长度 1，next[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] = k+1，k 也同步加 1。
• 若 pattern[i] 不等于 pattern[k]，说明不能简单地延长。此时已知前缀串 pattern[0..k-1] 里仍然存在更短的相等前后缀，这正是 next[k-1]，我们把 k 回退到 next[k-1]，然后再次比较 pattern[i] 和 pattern[k]，如果还不行就继续回退，直到 k=0 或者匹配成功。

你可能已经发现，这个回退过程和匹配失败时的主循环是一模一样的。这就是 KMP 设计最精妙的地方：计算 next 的过程，本质上是让模式串自己和自己做匹配，从而把模式串的每一个字符对应的回退信息都提前算好。

用代码写出来就是：

vector<int> getNext(const string& p) { int n = p.size(); vector<int> 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 遍历 text，j 遍历 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; vector<int> 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) { vector<int> 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 到 nextval

next 数组还有一个常见变体叫 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 后，喜欢把它写得很花哨，一行代码解决很多事，看起来很厉害，但之后自己看都费劲。我个人的看法是，重点是性能和逻辑正确，而不是代码短。

下面这个版本是我放在自己代码库里最常拿出来用的，兼顾清晰和性能：

vector<int> prefixFunction(const string& p) { int n = p.size(); vector<int> 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; vector<int> 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 = "abababa"，pattern = "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 自动机都会轻松很多。