KMP算法详解：从暴力匹配到高效字符串匹配的工程实践

前段时间帮一个做日志检索系统的朋友排查线上问题，几十万条日志里拿一组关键词做匹配，用暴力搜的方式跑了一次，整个服务响应时间直接翻了几倍。我当时跟他说，这种情况不用上什么复杂框架，先把字符串匹配算法换成KMP，问题基本就能缓解。他当时还半信半疑——一个教科书里的老算法，真能立竿见影？最后换完效果确实明显，性能提升了一个量级。从那之后我只要有时间，就会给团队里的新人系统讲一遍KMP，因为它不仅仅是“一个字符串匹配算法”，更是理解“用空间换时间”“状态转移思想”“如何从暴力解法中找到重复劳动”的极好样板。

KMP全称是Knuth-Morris-Pratt算法，由D.E.Knuth、J.H.Morris和V.R.Pratt在1977年联合发表。这个算法解决的核心问题非常朴素：在一段长文本中查找某个模式串是否出现、出现在哪里。它的亮点在于，当某次字符比较失败时，主串指针不回溯，而是利用已经匹配过的信息，让模式串跳到更靠后的位置继续比较。这个“不回溯”的机制，是所有优化思路的起点，也是很多刚接触算法的同学最难跨过的一道坎。

这篇文章我会毫无保留地把KMP从原理到代码再到工程实践中的坑，完整地过一遍。内容包括最关键的next数组计算、不同教材里next数组定义的差异、C++和Python两种语言的完整实现、常见的调试陷阱、以及如何把KMP用在循环节判定等高频场景。无论你是刚学数据结构与算法的学生，还是工作中需要频繁处理文本匹配的开发者，这篇文章都能帮你少走不少弯路。

1. 为什么字符串匹配会卡死项目：从暴力匹配说起

1.1 暴力匹配的工作方式与痛点

暴力匹配的思路非常直接：对于主串S，从第一个字符开始，尝试与模式串P的第一个字符对齐，然后逐个比较。一旦发现某个字符不匹配，就把模式串整体向右移动一位，再用模式串的第一个字符与主串的下一个字符对齐，重新开始比较。

这个过程如果用生活化的类比来解释，就像你在读一本书，想在书里找到某句话。暴力匹配的做法是：每翻到一页，就从页首开始逐字比对；如果中间某个字对不上，就只往后挪一个字，再从页首开始重新读。比如主串是"ABABABCAB"，模式串是"ABABC"，暴力匹配从主串第0位开始，前4个字符A、B、A、B都匹配，第5个字符主串是A，模式串是C，不匹配。于是模式串整体后移一位，从主串第1位开始重新比较。每次失配就只移动一位，已经比较过的字符完全没有被利用起来，这是暴力匹配最大的浪费。

它的时间复杂度很好算：主串长度为n，模式串长度为m，最坏情况下每移动一次模式串都要完整比较m个字符，总比较次数是O(n×m)。当主串达到几十万甚至上百万字符时，这个复杂度会直接拖垮性能。我之前见过一个最惨烈的例子：模式串是"AAAAAAAB"，主串是几万字符的重复"A"串，暴力匹配在这里几乎退化成O(n×m)，跑一次要好几秒，完全没法用。

1.2 一次失败的“安抚式”优化为何不靠谱

有些同学会说，那我加个简单优化：先比较模式串的第一个字符，如果第一个字符不同就直接跳过。这个优化看起来解决了部分问题，但只对模式串首字符在文本中很少出现的场景有效。一旦文本里首字符密度很高，比如搜索字母"a"开头的单词，这种优化基本等于没优化。

还有人会想，那我记录一下上次匹配失败的位置，失败的时候多移几位？这个思路方向是对的，但如果没有系统的理论支撑，很容易写出bug。这里要引出关键概念——已匹配的前缀。当我们在某次比较中，模式串的前k个字符都匹配成功，第k+1个字符失配时，我们其实已经知道了主串中这一段区间的确切内容，因为它和模式串的前k个字符完全一样。这k个字符里隐藏着下一次对齐位置的全部信息，能不能用好这些信息，决定了优化效果的上限。

1.3 KMP到底在优化什么

KMP算法的核心思想说白了就是三句话：主串指针绝不回退；模式串的移动位数不再固定为1；移动位置由模式串自身的结构决定。这个“自身的结构”指的就是模式串的前缀与后缀的重复关系。

举个例子，模式串是"ABABC"，当匹配到第5个字符失配时，我们已经知道主串当前位置之前的4个字符是"ABAB"。KMP的做法是，利用“ABAB”的前缀"AB"和后缀"AB"重叠这一点，让模式串直接滑动到让这个重叠部分对齐的位置，而不是只挪动一位。也就是说，模式串直接向后滑动2位（而不是1位），把模式串的XAB...与主串的XAB...对齐，然后继续从模式串第3个字符开始比较。整个过程主串指针完全不动，没有浪费任何一次已经完成的比较。

这句话是不是感觉有点绕？别急，核心就是“模式串自己身上的重复结构”决定了它可以跳多远。而这个重复结构，被KMP算法预计算成了一张表——准备阶段做一次O(m)的预处理，匹配阶段做到O(n)，整体时间复杂度O(n+m)。对于短模式串、长主串的场景，这种预处理成本极低，收益却非常明显。

2. 核心武器：next数组到底怎么算

2.1 next数组的含义

KMP算法里最核心的数据结构就是next数组，也叫部分匹配表或失配函数。next数组的长度跟模式串一样长，next[i]表示：当模式串的第i位字符与主串对应位置失配时，模式串应该跳到哪个位置继续比较。

这里有几个定义细节必须严谨。其实真正跳转的位置，取决于你用的是“next数组表示前后缀最大重叠长度”还是“next数组表示失配时模式串指针应该回退到的位置下标”。这两种表达之间就差一个1。很多刚学的同学就是被这两个版本绕晕的，后面我会详细区分。

先说最常见的、教科书里用的“下标0为-1”的版本。在这种约定下：

• next[0] = -1，表示第一个字符就失配时，模式串无法在当前位置继续匹配，主串指针需要右移一位；
• next[i]表示模式串前i个字符组成的子串中，最长相等前后缀的长度，特别地，这个长度包含了“子串本身不能作为自己的前后缀”的限制，也就是说最长相等前后缀长度小于等于i-1；
• 当第i位失配时，模式串跳转的位置就是next[i]。

如果你用的是“部分匹配值”的版本，那next[i]的含义就变成了“模式串前i个字符组成的子串，其最长相等前后缀的长度”。在匹配阶段，如果第i位失配（i从1计数），模式串下标跳转到next[i-1]的位置继续比较。

举个例子，模式串"ABABC"：

• 前1个字符"A"，没有真前后缀，最长相等前后缀长度为0（或按-1版本记next[0] = -1）；
• 前2个字符"AB"，前缀"A"、后缀"B"不等，最长相等前后缀长度为0；
• 前3个字符"ABA"，前缀"A"和后缀"A"相等，长度1；前缀"AB"和后缀"BA"不等，所以最长相等前后缀长度为1；
• 前4个字符"ABAB"，前缀"AB"和后缀"AB"相等，长度2；前缀"ABA"和后缀"BAB"不等，所以最长相等前后缀长度为2；
• 前5个字符"ABABC"，没有相等的前后缀，长度为0。

所以这个模式串的next数组（下标从0开始计数，next[0] = -1的版本）是[-1, 0, 0, 1, 2]。

2.2 手算next的完整推导

手算next数组有个非常简单的办法：把模式串的所有前缀子串都列出来，然后对每个前缀，找它的最长相等前后缀长度。

比如模式串"ABCDABD"，我们逐个前缀分析：

• 前缀"A"，最长相等前后缀长度为0；
• 前缀"AB"，前缀A、后缀B不等，长度为0；
• 前缀"ABC"，同理长度为0；
• 前缀"ABCD"，长度为0；
• 前缀"ABCDA"，前缀A和后缀A相等，长度为1；
• 前缀"ABCDAB"，前缀AB和后缀AB相等，长度为2；
• 前缀"ABCDABD"，长度为0。

所以部分匹配值表就是[0, 0, 0, 0, 1, 2, 0]。如果按next[0] = -1的失配跳转表来写，就是[-1, 0, 0, 0, 0, 1, 2]。

这里有个关键易混点：部分匹配表第i项，表示的是“模式串前i+1个字符组成的前缀串”的最长相等前后缀长度。而next[i]=部分匹配表[i-1]（当i>0时）。两者就差一个下标平移。如果你在代码里发现匹配结果不对，第一时间检查是不是把这两个概念搞混了。

我在教新人的时候，会让他们先用纸笔把"ABABACA"这种带重复字符的模式串手算一遍next数组，再拿代码跑一遍比对结果。这个过程能迅速暴露概念混淆的问题。

2.3 next计算中99%的人会踩的边界

手算的时候，边界条件很容易被忽略。比如模式串的第一个字符失配时，next[0]在有-1约定的版本中是-1。为什么要专门设一个-1？因为当next[0] = -1时，代码里可以统一处理“主串指针i和模式串指针j都加1”的情况。

假设主串是"BCABC"，模式串是"ABC"。模式串第0位是'A'，主串第0位是'B'，不匹配。如果next[0]不设成-1，代码就需要单独判断j==0的情况，逻辑上会多一层分支。设成-1之后，匹配循环里出现j == -1时，直接让i和j都加1，逻辑非常统一。

还有一个边界问题是模式串长度为1的情况。next数组的长度为1，next[0] = -1。匹配逻辑要确保不会访问next数组越界。在while循环里，j = next[j]这行代码，当j = -1时就应该跳出，绝对不能拿-1去索引数组。

2.4 不同教材的next定义差异

我当年在《数据结构》教材里学的版本，next[1] = 0（下标从1开始计数），next数组的含义是“当前位失配时，模式串应该跳转到的位置，也等于前缀字符串的最长相等前后缀长度加1”。而网上很多教程用的是next[0] = -1（下标从0开始计数）的版本。这两种写法本质上等价，但处理边界时很不一样。

会不会带来实际影响？会。你看别人的代码时，如果不知道对方用的是哪个版本的next定义，很容易把“部分匹配表”直接当成“跳转表”来用，结果就是匹配结果错误或者数组越界。我的建议很简单：认准一种版本并吃透它，读写代码时先识别对方版本的约定。我自己在所有项目里统一用next[0] = -1、下标从0开始计数的版本，因为它代码写起来最省心，边界处理也最少。

3. 代码实现：C++与Python的完整写法

3.1 C++实现（含next求解和匹配）

next数组的求解过程本身就是一个小型的“自我匹配”过程。我们用一个指针j表示当前已匹配的前缀长度，i表示正在计算next[i]的位置。这里直接给出一份完整可运行的C++代码。

#include <iostream> #include <vector> #include <string> using namespace std; // 构建next数组，下标从0开始，next[0] = -1 vector<int> buildNext(const string& p) { int m = p.size(); vector<int> next(m, 0); if (m == 0) return next; next[0] = -1; int j = 0; int k = -1; while (j < m - 1) { if (k == -1 || p[j] == p[k]) { ++j; ++k; next[j] = k; } else { k = next[k]; } } return next; } // KMP匹配：返回模式串在主串中首次出现的下标，找不到返回-1 int kmpSearch(const string& s, const string& p) { int n = s.size(); int m = p.size(); if (m == 0) return 0; vector<int> next = buildNext(p); int i = 0; // 主串指针 int j = 0; // 模式串指针 while (i < n) { if (j == -1 || s[i] == p[j]) { ++i; ++j; } else { j = next[j]; } if (j == m) { return i - j; // 匹配成功，返回起点 } } return -1; } int main() { string text = "ABABABCABABD"; string pattern = "ABABC"; int pos = kmpSearch(text, pattern); cout << pos << endl; // 输出 2 return 0; }

这个实现里最精巧的地方在于buildNext中使用了双指针j和k。k有两种含义：一是当前最长的相等前后缀长度，二是回退的目标位置。初始化时k = -1，代表没有匹配的前后缀。当p[j] == p[k]时，说明当前字符可以延长前后缀匹配，于是j和k同时前进，把next[j]赋值为k。当不匹配时，k回退到next[k]，类似匹配阶段主串指针不回溯、模式串指针回溯的思想。

这里要特别注意一个细节：buildNext的循环条件是j < m - 1，不是j < m。因为循环体内每次都会先自增j，再给next[j]赋值，如果j已经是m-1，自增后变成m，就会越界。初学阶段这种下标越界bug最隐蔽，加了地址消毒工具（比如AddressSanitizer）可能直接崩溃，不崩溃的就会读到野值，产生错误结果。

3.2 Python实现及与C++的差异

Python的Python风格写法和C++略有不同，但核心逻辑完全一致。我给出一份简洁实现，并特意保留了更接近C++风格的写法，方便语言对照。

def build_next(p: str): m = len(p) nxt = [0] * m if m == 0: return nxt nxt[0] = -1 j, k = 0, -1 while j < m - 1: if k == -1 or p[j] == p[k]: j += 1 k += 1 nxt[j] = k else: k = nxt[k] return nxt def kmp_search(s: str, p: str) -> int: n, m = len(s), len(p) if m == 0: return 0 nxt = build_next(p) i = j = 0 while i < n: if j == -1 or s[i] == p[j]: i += 1 j += 1 else: j = nxt[j] if j == m: return i - j return -1 if __name__ == "__main__": text = "ABABABCABABD" pattern = "ABABC" print(kmp_search(text, pattern)) # 输出 2

Python写这个算法有一个隐藏的性能问题：如果p[j]和p[k]的访问非常频繁，字符串的__getitem__方法有一定开销。在模式串极长（比如上万字符）时，这个开销会被放大。工程中如果P是用bytes类型表示的二进制数据，访问效率会更高一些。但一般情况下，CPython解释器对字符串索引访问做过优化，直接用字符串问题不大。

还有一个和C++的差异是：Python的列表天然支持负索引，如果你不小心把next数组中的-1直接当作索引使用，Python不会报数组越界，而是会取到列表倒数第一个元素。这个bug隐蔽性极高——程序不会崩溃，但结果会莫名其妙地错。比如next[k]当k = -1时，实际访问的是nxt[-1]也就是nxt[m-1]，完全不是想要的回退位置。所以Python版本里，对k == -1的判断必须在访问nxt[k]之前完成。

3.3 用nextval优化：什么时候用，什么时候不用

next数组还有一个著名的优化版本，叫nextval数组。它解决的是“多重回退”问题。比如模式串是"AAAAB"，部分匹配表是[0, 1, 2, 3, 0]，对应的next数组（-1版本）是[-1, 0, 1, 2, 0]。假设在第4位（下标3，字符A）失配，跳转到next[3] = 2，即模式串下标2（也是字符A）的位置。这时候会再次失配，因为模式串第2位的字符A和第4位的字符A一样。所以还得继续跳转到next[2] = 1，再跳转到next[1] = 0，最后到next[0] = -1。这一串跳转其实可以通过预处理一次到位：如果模式串在跳转前后的字符相同，就直接继承跳转目标的next值。

代码里对应的改动是在buildNext里赋值next[j]之后，再加一层判断：

if (p[j] != p[k]) { next[j] = k; } else { next[j] = next[k]; }

这里有个容易弄反的地方：如果p[j] == p[k]，你要让next[j]等于next[k]，而不是仍然等于k。因为下一步失配时跳到k还是会被同一个字符卡住，不如直接跳到next[k]能落到的更早位置。这相当于对失配跳转做了一次路径压缩，类似并查集的路径压缩思想。

nextval这个优化通常能使匹配效率小幅提升，尤其适合模式串中有大量连续重复字符的场景。不过在实际工程中，如果模式串长度不长（比如几十个字符），性能差异几乎可忽略，没必要为了这个优化增加代码复杂度。但你要是写算法竞赛、或者处理超长模式串的分词系统，建议直接上nextval。

3.4 测试用例设计思路

写代码容易，写对不易。我一般会设计四组测试用例来验证KMP实现的正确性。

第一组是基本匹配：主串"ABABABCABABD"，模式串"ABABC"，期望结果是2。

第二组是不匹配：主串"AAAAA"，模式串"AAAAB"，期望结果是-1。这组能验证当模式串中大量重复前缀导致多重回退时，next数组能否正确工作。

第三组是模式串只在主串末尾出现：主串"ABCABCABCD"，模式串"ABCD"，期望结果是6。这覆盖了匹配成功时j刚好等于m的场景，能验证返回值i - j是否计算正确。

第四组是模式串是单个字符且该字符不存在：主串"ABCDEFG"，模式串"H"，期望结果是-1。这能检查模式串长度为1时，next数组初始化是否正确。

这四组跑过之后，我再拿更随机的长串做一次暴力对比测试：随机生成长度为10000的主串和长度为10到100的模式串，同时跑KMP和暴力匹配，比对结果。这个随机对比是判断实现正确性的金标准，强烈建议所有人在写完KMP之后都做一遍。

4. 实战中KMP的关键细节与避坑

4.1 边界条件最容易出错的地方

代码写完后，真正在工程里运行，最常见的崩溃或越界场景集中在以下几处。

第一，模式串为空。某些业务场景下模式串可能来自外部输入，如果为空字符串，buildNext里直接返回空数组，kmpSearch里j初始化为0，while循环条件为j == -1或s[i] == p[j]，p[j]这里数组越界。所以KMP代码必须专门处理m == 0的情况，我习惯直接返回0，表示空串出现在主串任何位置。

第二，主串指针i在匹配成功那一刻是否越界。在while (i < n)的循环内，如果主串最后一个字符刚好让模式串匹配完成，i会先自增到n，然后进入if (j == m)分支返回结果。这时的返回值i - j = n - m，正好是有效位置。

第三，next数组构建中的k = next[k]是否可能死循环。理论上不会，因为next[k]一定小于k，回退路径必然有尽头。但如果next数组初始化不对，比如初始值设成了0而不是-1，在模式串首字符重复的场景下，k = next[k]可能反复指向同一个位置，造成死循环。所以next[0]的初始化必须单独处理，不能和普通位置混在一起。

4.2 时间复杂度简单分析

KMP的时间复杂度可以从两个层面分析。构建next数组时，每个字符最多被比较常数次，j和k的回退本质上是对之前计算结果的复用，所以预处理时间是O(m)。匹配过程中，主串指针i只增不减，模式串指针j虽然会回退，但每次回退到next[j]时，都意味着至少一个已匹配的字符被“释放”，而这些释放次数加起来不会超过i的推进次数，总体复杂度是O(n)。两个阶段加起来是O(n+m)，比暴力匹配的O(n×m)有了本质提升。

空间复杂度也很容易理解：只需要存储一个长度为m的next数组，所以是O(m)。在实际使用时，这个额外内存几乎可以忽略。

4.3 面试中的变式考察：最小循环节等

KMP在面试和算法竞赛里经常作为“前菜”出现，真正考的是它的一堆变式。最常见的变式是判断一个字符串是否由某个子串循环构成，以及求最小循环节长度。做法一句话就能讲完：设字符串长度为L，令k = L - next[L]（这里的next[L]表示整个字符串的最长相等前后缀长度，可以在构建next时多算一位）。如果L能被k整除，那么该字符串的最小循环节长度就是k，否则说明它不能由某个更短子串循环构成。

为什么有效？因为next[L]存储的是整个字符串的前缀与后缀重叠的最长长度，L - next[L]得到的“剩余部分”恰好是循环结构的周期。举个例子，字符串"ABCABCABC"，L=9，最长相等前后缀是"ABCABC"，长度6，k = 3，正好是最小循环节"ABC"的长度。再比如"ABABAB"，L=6，最长相等前后缀"ABAB"，长度4，k=2，正好是"AB"。

类似的变式还有统计模式串在文本中出现的次数（允许重叠或不允许重叠），只需要在匹配成功一次之后，让j回退到next[j]而不是直接清零，就能继续在不回溯主串的情况下找到下一次出现位置。这些变式本质都源于对next数组的深入理解，面试时如果能把它们背后的推导逻辑讲清楚，比背代码要加分得多。

4.4 什么时候不要用KMP

尽管KMP很优秀，但它并不是所有字符串匹配问题的最优解。如果模式串非常短（比如1到3个字符），暴力匹配或memchr这类系统级搜索函数的常数极小，甚至比KMP还快。原因在于KMP需要预处理next数组，访问模式串和主串时还有额外跳转逻辑，这些开销在短模式串场景下会抵消掉算法时间复杂度上的优势。

另外，如果匹配需求是“在一个大文本中同时查找多个模式串”，KMP就不是最优方案了。这时更合适的是AC自动机（Aho-Corasick），它相当于把多个模式串的KMP状态转移图合并到一棵Trie树里，一次扫描可以把所有模式串都找出来。我做过一次日志告警系统升级，模式串从几个变成几百个，KMP直接扛不住，换成AC自动机之后表现非常稳定。

还有一种场景是模式串和文本都可能动态变化，比如文本编辑器里的“实时查找”功能。这种情况更适合用Horspool算法或Sunday算法这类基于坏字符跳转的算法，它们在实际文本上往往比KMP跳得更远，常数也更小。

5. 常见问题速查表与实操心得

5.1 常见问题速查表

我在带新人和给团队做代码评审时，把KMP相关的典型问题整理成了一份速查表，方便快速定位问题。

5.2 调试技巧：把next数组打印出来

我调试KMP时的一个习惯是：先打印模式串的next数组，再拿一个短主串手动模拟整个过程。比如模式串"ABABAC"的next数组是[-1, 0, 0, 1, 2, 3]，打印出来看一眼就能确认构建逻辑是否正常。

如果在匹配阶段结果仍然不对，我会在while循环里临时加一行输出，打印i、j、s[i]、p[j]这四个值，然后手动模拟每一步跳转。KMP的状态跳转是确定的，手动模拟和程序输出一对比，很快就能定位是next数组的问题还是匹配循环的逻辑问题。

还有一个实用技巧：写一个测试脚本，随机生成大量主串和模式串，再用暴力匹配和KMP各跑一遍，比对结果。这个脚本我几乎每次写字符串算法都会用，它能覆盖掉手工用例根本想不到的边界组合。

5.3 学习路径建议

如果你刚接触KMP，我建议按这个顺序来：先不看任何代码，拿一个简单模式串比如"ABABAC"，用纸笔手动模拟一次匹配过程，感受一下“主串指针不回溯”到底是怎么回事；然后手算next数组，用不同模式串反复练习；再照着代码自己敲一遍，不要复制粘贴，敲完拿前面的随机对比脚本验证；最后尝试做几个变式题，比如找最小循环节、统计重叠出现次数。

如果你已经有基础，可以直接跳到nextval优化、AC自动机的理解。KMP和AC自动机之间的关系，很像“单个模式串的自动机”与“多个模式串的自动机”之间的关系，二者共享的状态转移思想，对理解更复杂的字符串算法非常有帮助。

根据我个人刷题和做项目的经验，学习KMP最大的障碍不是代码，而是“为什么可以这样跳”这个概念。只要把前缀后缀这件事彻底想明白，再去写代码和调试，效率会高非常多。我见过很多人在没理解原理的情况下硬背代码，结果过两天又忘了，遇到变式题更是一头雾水。所以千万别跳过手动模拟这一步。

写在最后的一些私货

这篇文章像这样从原理写到底层实现，其实主要是因为我自己当年学KMP的时候也踩过不少莫名其妙的坑，甚至一度怀疑是自己脑子不够用。后来带了几届实习生，发现大家的问题高度一致，基本都出在next数组的定义混淆、边界处理、以及不知道该如何验证代码正确性这三块。所以我把这些经验尽量详细地写了下来，希望能让后来的人少走几步弯路。

如果你现在正被KMP绕得头疼，不妨放下代码，拿个字符串在纸上画一画。画清楚了，剩下的就是机械操作。另外说句实在话，KMP在真实业务代码里的直接出场率并不算高，因为大多数语言的标准库已经在底层处理好了字符串查找。但如果你做的是搜索引擎、日志分析、代码编辑器、网络包检测这类对匹配性能敏感的系统，KMP的思想就非常重要了。它就像是你工具箱里的一把精密螺丝刀，平时可能吃灰，但真到需要的时候，没有其他工具能比它更顺手。