写 KMP 算法这篇文章，其实是我早就想做的事。字符串匹配是写代码几乎绕不开的一件事，不管你是刷 LeetCode、打信奥、做文本处理，还是写搜索引擎、做日志分析，KMP（Knuth-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）。我先把最标准的定义写清楚，后面所有推导都基于这个定义。
对于模式串 P，next[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 实际上是一直在充当“已经匹配的前缀的长度”的角色。具体的计算规则是这样的：我们从 i=1 一直算到 i=6，每一次都尝试把 P[i] 和 P[j] 比较：
- 如果相等，太好了，说明最长相等前后缀的长度可以扩展一位，所以 next[i] = j + 1，j 也跟着加一，然后 i 继续往后走。
- 如果不相等，就需要让 j 回退到 next[j-1]，再重新比较，直到 j=0 或者遇到相等的情况。如果 j 已经退到 0 还是比不成，那 next[i] = 0。
我们实际操作一下。
i=1，j=0，比较 P[1]='B' 和 P[0]='A'，不相等，j 已经为 0，所以 next[1]=0。"AB"确实没有相等前后缀。
i=2，j=0，比较 P[2]='A' 和 P[0]='A'，相等！所以 next[2]=j+1=1，同时 j 变成 1。你检查一下"ABA"，前缀"A"和后缀"A"确实相等，长度是 1。
i=3，j=1，比较 P[3]='B' 和 P[1]='B'，相等！next[3]=j+1=2，j 变成 2。"ABAB"的最长相等前后缀是"AB"，长度 2，没问题。
i=4，j=2，比较 P[4]='A' 和 P[2]='A'，相等！next[4]=j+1=3，j 变成 3。"ABABA"的最长相等前后缀是"ABA"，长度 3，没问题。
i=5，j=3，比较 P[5]='B' 和 P[3]='B'，相等！next[5]=j+1=4，j 变成 4。"ABABAB"的最长相等前后缀是"ABAB"，长度 4。
i=6，j=4，比较 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++ 的实现：
vector<int> buildNext(const string& pattern) { int m = pattern.length(); vector<int> 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] 回退，而且这个过程可能发生多次。
- 代码里没有特判 j==0 的情况，它自然地包含在 while 条件里：当 j==0 时，while 条件不成立，直接走后续的 if 判断。
这个写法是最经典的 next 数组求法，我建议你在自己的机器上一个字符一个字符地走一遍循环，搞清楚每次 j 的变化。
3. 匹配阶段的完整流程与复杂度分析
3.1 匹配阶段如何配合 next 数组
next 数组构建完成之后，匹配阶段反而简单了。同样维护两个指针，i 指向主串，j 指向模式串，规则如下：逐个比较 T[i] 和 P[j]；如果相等，两者都往后走；如果不等，j 回退到 next[j-1]（如果 j>0），而 i 不动；如果 j 已经等于 0 且仍然不等，说明模式串的第一位就对不上，直接让 i 往后走一位。
我写一个完整的匹配函数：
int kmpSearch(const string& text, const string& pattern) { int n = text.length(), m = pattern.length(); if (m == 0) return 0; vector<int> 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]。
一开始，i=0，j=0，T[0]='A' 等于 P[0]='A'，i 和 j 都加一；T[1]='B' 等于 P[1]='B'；T[2]='A' 等于 P[2]='A'；T[3]='B' 等于 P[3]='B'；T[4]='A' 等于 P[4]='A'；T[5]='B' 等于 P[5]='B'；T[6]='C' 等于 P[6]='C'，七位全部匹配成功，j 变成 7，等于 m，返回 i - m + 1 = 6 - 7 + 1 = 0。模式串从主串下标 0 开始完全匹配。
假设换一种情况，主串 T ="ABABABABC"，模式串仍然是"ABABABC"。i 走到 6 的时候，T[6]='A'，P[6]='C'，不相等，此时 j=6，所以 j 回退到 next[5]=4，i 保持不变。然后比较 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(n+m)
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(n+m)，空间复杂度 O(m)，因为只需要存模式串的 next 数组。跟暴力匹配 O(n×m) 相比，优势一目了然。不过我要补一句：KMP 的常数因子不算小，在普通的随机文本场景下，暴力匹配的表现未必比 KMP 差，甚至可能更快。KMP 真正的价值，体现在最坏情况有保证的基础上——无论输入数据长什么样，它都能保证在 O(n+m) 时间内完成。这正是竞赛选手和底层库作者特别看重它的一点：最坏情况足够可控。
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]=2，P[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 数组的推导亲手练到滚瓜烂熟，然后在一道道题目里慢慢体会它的妙处。
