1. 字符串匹配的暴力解法为什么不够用

做C++开发这些年，字符串处理几乎是绕不开的日常。日志检索、协议解析、文本编辑器的高亮引擎、甚至数据库的LIKE查询底层，到处都有子串匹配的影子。很多人第一次写子串查找，脑子里蹦出来的就是两层循环：外层遍历主串的每个起点，内层逐字符比对模式串。这个思路没错，逻辑也对，但它的时间复杂度是O(n*m)，n是主串长度，m是模式串长度。主串几十万字符、模式串几千字符的时候，这个平方级的开销会直接把程序拖垮。

我最早踩这个坑是在做一个日志分析工具的时候。当时需要从几百万行的日志里筛出包含特定错误码前缀的行，用的就是暴力匹配。单条日志不长，跑起来没啥感觉，但一旦把整个日志文件读进来做全量扫描，CPU直接飙满，一次完整扫描要等十几秒。后来换成KMP，同样的数据量，耗时降到了不到一秒。这个差距不是靠优化编译器或者换更快的机器能弥补的，它是算法层面的降维打击。

KMP这三个字母来自三位发明者的姓氏首字母，全称是Knuth-Morris-Pratt算法。它的核心贡献在于：当匹配失败时，主串的指针不回退，只移动模式串的指针。暴力匹配之所以慢，就是因为每次失配都要把主串指针往回拉，从头再来。KMP通过预处理模式串，提前算出一张“失配跳转表”，让模式串在失配时能跳到最合理的位置继续比对，而不是傻乎乎地只往右挪一格。

这篇文章面向的是有一定C++基础、想彻底搞懂KMP并拿到一份能直接用的完整实现的读者。我会从next数组的构建讲起，把每个下标背后的含义掰开揉碎，然后给出完整可编译的代码，最后分享几个我在实际使用中踩过的坑和优化技巧。你不需要有竞赛背景，只要会写基本的C++循环和数组操作，就能跟上。

2. KMP的核心思路拆解

2.1 从暴力匹配的痛点说起

先看暴力匹配的典型写法。假设主串是text，模式串是pattern，代码大概长这样：

int bruteForce(const string& text, const string& pattern) { int n = text.size(), m = pattern.size(); 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; }

这段代码的问题在于，当text[i+j] != pattern[j]时，外层循环的i只往前挪一格，内层已经比对过的j个字符的信息完全被丢弃了。举个例子，主串是"ABABABC"，模式串是"ABABC"。当比对到第五个字符时，text[4]='B'和pattern[4]='C'失配。暴力做法是把i从0挪到1，然后从text[1]开始重新和pattern[0]比。但实际上，我们已经知道text[0..3]是"ABAB"，这段信息完全可以用来避免重复比对。

KMP的洞察就在这里：失配时，模式串的前缀和主串已经匹配的那部分后缀之间，可能存在重叠。这个重叠的长度决定了模式串可以向右滑动多少格而不遗漏可能的匹配。next数组就是用来记录这个“最长相等前后缀”长度的。

2.2 next数组到底在记录什么

next数组是KMP的灵魂，也是最容易让人迷糊的地方。不同教材对next数组的定义有细微差别，有的叫next，有的叫prefix function，有的叫failure function。我这里采用最直观的一种定义：next[i]表示模式串pattern[0..i]这个子串中，最长的相等前后缀的长度。

什么叫相等前后缀？以"ABABC"为例，看它的前缀"ABAB"。这个子串的前缀有"A"、"AB"、"ABA"，后缀有"B"、"AB"、"BAB"。其中"AB"既是前缀也是后缀，长度是2。所以对于pattern[0..3]即"ABAB"，它的最长相等前后缀长度是2。

再比如"AAAA"，前缀有"A"、"AA"、"AAA"，后缀有"A"、"AA"、"AAA"。最长相等前后缀是"AAA"，长度3。注意这里前后缀不能取整个字符串本身，否则任何字符串的最长相等前后缀都是它自己，那就没意义了。

next数组的构建过程本质上是一个递推。假设我们已经知道了next[i-1]的值，现在要算next[i]。如果pattern[i] == pattern[next[i-1]]，那么next[i] = next[i-1] + 1。如果不相等，就往前找更短的相等前后缀，也就是看next[next[i-1] - 1]，一直回溯到匹配或者回到0为止。这个过程用代码表达就是：

vector<int> buildNext(const string& pattern) { int m = pattern.size(); vector<int> next(m, 0); int len = 0; // 当前最长相等前后缀长度 int i = 1; while (i < m) { if (pattern[i] == pattern[len]) { len++; next[i] = len; i++; } else { if (len != 0) { len = next[len - 1]; } else { next[i] = 0; i++; } } } return next; }

这段代码里有个细节值得注意：当len != 0且字符不匹配时，我们执行的是len = next[len - 1]，而不是直接len = 0。这是因为可能存在更短的相等前后缀。比如模式串是"AABAAAB"，在某个位置失配后，虽然当前长度的前后缀不匹配，但缩短一点可能就匹配了。这个回溯过程保证了next数组的正确性。

2.3 匹配阶段如何利用next数组

有了next数组，匹配阶段的逻辑就清晰了。主串指针i从头到尾只往前走，从不回退。模式串指针j在失配时根据next数组跳转：

int kmpSearch(const string& text, const string& pattern) { vector<int> next = buildNext(pattern); int n = text.size(), m = pattern.size(); int i = 0, j = 0; while (i < n) { if (text[i] == pattern[j]) { i++; j++; if (j == m) { return i - m; // 找到匹配，返回起始下标 } } else { if (j != 0) { j = next[j - 1]; } else { i++; } } } return -1; }

这里的关键在于j = next[j - 1]这一行。当text[i]和pattern[j]失配时，我们知道pattern[0..j-1]已经和text[i-j..i-1]匹配上了。next数组告诉我们，pattern[0..j-1]的最长相等前后缀长度是next[j-1]，所以我们可以把模式串向右滑动，让它的前缀对齐到刚才匹配部分的后缀上，然后从pattern[next[j-1]]继续和text[i]比对。主串指针i纹丝不动。

整个KMP算法的时间复杂度是O(n+m)，构建next数组O(m)，匹配O(n)。空间复杂度O(m)，就是next数组的开销。相比暴力匹配的O(n*m)，这是质的飞跃。

3. 完整C++实现与逐行解析

3.1 基础版本：返回第一个匹配位置

下面这份代码是我在实际项目中反复使用后整理出来的，去掉了花哨的模板技巧，保留了最核心的逻辑，同时加上了必要的边界处理：

#include <iostream> #include <string> #include <vector> using namespace std; // 构建next数组 vector<int> buildNext(const string& pattern) { int m = pattern.size(); vector<int> next(m, 0); int len = 0; int i = 1; while (i < m) { if (pattern[i] == pattern[len]) { len++; next[i] = len; i++; } else { if (len != 0) { len = next[len - 1]; } else { next[i] = 0; i++; } } } return next; } // KMP查找，返回第一个匹配的起始下标，找不到返回-1 int kmpSearch(const string& text, const string& pattern) { if (pattern.empty()) return 0; if (text.size() < pattern.size()) return -1; vector<int> next = buildNext(pattern); int n = text.size(); int m = pattern.size(); int i = 0, j = 0; while (i < n) { if (text[i] == pattern[j]) { i++; j++; if (j == m) { return i - m; } } else { if (j != 0) { j = next[j - 1]; } else { i++; } } } return -1; } int main() { string text = "ABABABCABABABCABABABC"; string pattern = "ABABC"; int pos = kmpSearch(text, pattern); if (pos != -1) { cout << "匹配位置: " << pos << endl; } else { cout << "未找到匹配" << endl; } return 0; }

编译运行这段代码，输出是匹配位置: 2。主串中"ABABC"第一次出现的位置确实是下标2。你可以把主串和模式串换成任意内容测试，逻辑都是通的。

3.2 进阶版本：找出所有匹配位置

实际工作中，我们往往需要找出所有出现的位置，而不是只找第一个。改动很小，把找到匹配后的return改成记录位置并继续搜索即可：

vector<int> kmpSearchAll(const string& text, const string& pattern) { vector<int> result; if (pattern.empty()) return result; if (text.size() < pattern.size()) return result; vector<int> next = buildNext(pattern); int n = text.size(); int m = pattern.size(); int i = 0, j = 0; while (i < n) { if (text[i] == pattern[j]) { i++; j++; if (j == m) { result.push_back(i - m); j = next[j - 1]; // 继续找下一个匹配 } } else { if (j != 0) { j = next[j - 1]; } else { i++; } } } return result; }

注意j = next[j - 1]这一行。找到一次匹配后，我们不能把j直接置0，因为模式串的前缀可能和已经匹配部分的后缀重叠，下一个匹配可能紧接着就开始了。比如主串"AAAAA"，模式串"AAA"，匹配位置有0、1、2三个。如果找到位置0后把j置0，就会漏掉位置1和2。

3.3 next数组的另一种写法：统一减一

网上流传的KMP代码里，next数组有两种常见定义。我上面用的是“最长相等前后缀长度”版本，next[i]的值直接就是长度。另一种是“统一减一”版本，next[i]存的是长度减一，匹配时用j = next[j]而不是j = next[j-1]。两种写法等价，但混用会导致bug。

统一减一版本的构建代码：

vector<int> buildNextMinusOne(const string& pattern) { int m = pattern.size(); vector<int> next(m, -1); int j = -1; int i = 0; while (i < m - 1) { if (j == -1 || pattern[i] == pattern[j]) { i++; j++; next[i] = j; } else { j = next[j]; } } return next; }

这种写法的好处是匹配循环里少一次减法，代码看起来更简洁。但缺点是next[0]初始化为-1，理解起来稍微绕一点。我个人更推荐第一种写法，因为“长度”这个语义更直观，调试的时候不容易搞混。

注意：不管你用哪种写法，整个项目里必须统一。我见过有人在构建时用长度版本，匹配时用减一版本，结果程序在小数据上碰巧能跑，大数据上各种越界和错位，排查了大半天才发现是定义混用。

4. 实际使用中的坑与优化技巧

4.1 空模式串和越界问题

空模式串是个容易被忽略的边界。按照字符串匹配的惯例，空模式串应该匹配任何位置，返回0。但如果你在buildNext里不做处理，pattern.size()为0时，vector<int> next(0)是合法的，但后面的循环while (i < m)直接不执行，返回空数组。到了匹配阶段，pattern[j]会访问越界。所以我在kmpSearch开头加了if (pattern.empty()) return 0;。

另一个越界点是text.size() < pattern.size()的情况。如果主串比模式串还短，根本不可能匹配，直接返回-1，省去后续所有计算。这个判断在kmpSearchAll里同样需要。

4.2 字符集与编码问题

KMP算法本身对字符集没有要求，它只关心字符是否相等。但实际使用时，如果处理的是UTF-8编码的中文文本，一个汉字占3个字节，按字节比对可能会在汉字中间切断，导致匹配结果不符合预期。比如模式串是“中国”，主串是“我爱中国”，按字节匹配没问题，因为“中国”的UTF-8字节序列是固定的。但如果模式串是“国中”，按字节匹配可能会在某个汉字的中间字节处错误匹配。

处理多字节编码的正确做法是先把字符串转换成宽字符或者Unicode码点数组，再对码点数组做KMP。C++里可以用std::wstring配合std::wstring_convert，或者用第三方库如utf8cpp。如果只是做ASCII文本匹配，直接用std::string就够了。

4.3 性能实测与优化方向

我在一台普通开发机上做了个简单测试：主串是随机生成的100万个字符，模式串长度100，暴力匹配平均耗时约2.3秒，KMP平均耗时约0.08秒。差距接近30倍。如果模式串更长，比如长度1000，暴力匹配会飙升到20秒以上，KMP仍然稳定在0.1秒左右。

KMP还有进一步优化的空间。比如next数组的构建可以合并到匹配过程中，节省一次O(m)的预处理。但这样代码可读性会下降，除非对性能有极致要求，否则不建议。另一个优化是使用std::string_view代替const string&，避免不必要的拷贝。C++17及以上版本可以直接用：

int kmpSearch(string_view text, string_view pattern) { // 逻辑不变，只是参数类型换了 }

string_view不拥有字符串，只是引用，传参开销极小。但要注意生命周期问题，确保被引用的字符串在函数执行期间有效。

4.4 常见问题速查表

实操心得：调试KMP的时候，把next数组打印出来是最有效的排查手段。拿一个短模式串，手动算一遍next数组，和程序输出对比。如果对不上，问题一定出在构建阶段。构建对了，匹配阶段基本不会错。

5. 从KMP延伸出去的几个实用场景

5.1 字符串周期检测

KMP的next数组有个很妙的用途：判断一个字符串是否由某个子串重复构成。如果next[m-1]的值大于0，且m % (m - next[m-1]) == 0，那么这个字符串就是由长度为m - next[m-1]的子串重复构成的。比如"ABCABCABC"，next[8] = 6，9 - 6 = 3，9 % 3 == 0，所以它由"ABC"重复3次构成。

这个性质在数据压缩和模式识别里很有用。我曾经用这个技巧检测日志文件里是否有周期性重复的异常模式，比正则表达式快得多。

5.2 在流式数据中做增量匹配

KMP的主串指针不回退特性，让它天然适合流式场景。你可以把KMP改造成一个状态机，每次喂入一个字符，返回当前是否匹配完成。这样处理网络数据包或者大文件分块读取时，不需要把整个数据加载到内存。

改造思路是维护一个j状态，每来一个字符就更新j，当j == m时报告一次匹配。状态机的核心逻辑和普通KMP完全一样，只是把循环拆成了单步调用。

5.3 与std::string::find的性能对比

C++标准库的std::string::find底层实现因编译器而异。GCC的libstdc++用的是改进的暴力匹配，在某些情况下性能不如KMP。Clang的libc++实现也类似。如果你在做高频字符串查找，自己实现KMP往往能获得更稳定的性能表现。不过对于短字符串，标准库的find因为常数因子小，可能反而更快。我的经验是：模式串长度超过50，或者需要反复查找同一模式串时，用KMP；否则直接用find。

5.4 多模式串匹配的过渡

KMP解决的是单模式串匹配问题。如果需要在同一主串里同时查找多个模式串，KMP就不够用了，得请出AC自动机。AC自动机可以看作是KMP在多模式串上的推广，它把多个模式串构建成一棵Trie树，然后在树上建立类似next数组的失配指针。理解了KMP的next数组，AC自动机的失配指针就很好理解了——无非是在树上找最长相等前后缀。

我在实际项目里遇到过一个需求：从用户输入中同时检测几十个敏感词。用KMP逐个匹配，每个词都要扫一遍主串，总复杂度是O(k*n)，k是敏感词数量。换成AC自动机后，一次扫描就能找出所有敏感词，复杂度降到O(n + 总模式串长度)。这个优化在敏感词数量多的时候效果非常明显。

6. 我个人的调试与验证方法

写KMP最容易出错的地方就是next数组。我自己的验证流程是这样的：先拿一个简单模式串，比如"ABABC"，手动算出next数组应该是[0,0,1,2,0]。然后写个测试函数把程序构建的next数组打印出来，对比是否一致。如果一致，再拿几个边界情况测试：全相同字符"AAAA"、无重复字符"ABCD"、单字符"A"、空串""。这几个用例覆盖了next数组构建的所有分支。

匹配阶段的验证，我会构造几组主串和模式串，手动推演匹配过程，确认返回的位置正确。特别要测试的是模式串在主串末尾匹配、模式串比主串长、主串中有多个重叠匹配这几种情况。

最后，我会用随机生成的字符串做压力测试。生成一个长主串和一个短模式串，分别用KMP和暴力匹配跑一遍，对比结果是否一致。如果几万组随机测试都一致，基本可以确认实现是正确的。这个方法虽然笨，但非常有效，我靠它抓出过好几个隐蔽的边界bug。

提示：随机测试的时候，字符集不要只限于大小写字母，把数字、符号、空格都加进去，能覆盖更多意外情况。我遇到过模式串包含空格时因为输入读取问题导致匹配失败的案例，后来在测试里专门加了带空格的用例。

代码这东西，看懂了和写对了之间隔着一条河。KMP的next数组构建那几行，我见过太多人背下来了但换个场景就不会写。真正理解每个下标背后的“最长相等前后缀”含义，比记住代码本身重要得多。上面这份实现你可以直接复制到项目里用，但建议至少手动敲一遍，把next数组打印出来看看，感受一下它是怎么随着模式串结构变化的。踩过这个坑，以后遇到字符串匹配的问题，你脑子里第一个蹦出来的就会是KMP，而不是两层for循环。