字符串匹配这件事说简单也简单说坑也真不少。暴力匹配写起来三行代码就能跑可一旦遇到主串长度上百万、模式串又带着大量重复前缀的场景比如日志检索、DNA序列比对、入侵检测规则匹配暴力法那种失配就回退到下一个起点的做法就会把时间复杂度拖到 O(n*m)跑起来肉眼可见地卡。KMP 算法就是专门治这个病的——它通过预处理模式串把失配后的回退位置提前算好让主串指针永不后退整体压到 O(nm)。这篇就把 KMP 的 C 实现从头到尾讲透包括 next 数组到底怎么求、为什么这么求、完整可编译代码、以及我自己在写的时候踩过的几个典型坑。不管你是刚学数据结构的学生还是工作中需要手写匹配逻辑的开发者都能直接拿去用。1. 为什么暴力匹配会在某些串上慢得离谱先把问题摆清楚不然体会不到 KMP 的价值。暴力匹配BFBrute Force的思路是从主串的每一个位置 i 开始尝试和模式串逐字符比对一旦失配i 回退到 i1模式串指针 j 归零重新来。int bruteForce(const string s, const string p) { int n s.size(), m p.size(); for (int i 0; i n - m; i) { int j 0; while (j m s[i j] p[j]) j; if (j m) return i; } return -1; }这段代码逻辑没问题问题出在回退上。考虑主串是aaaaaaaab模式串是aaab。每一轮比对前三个a都能匹配上到第四个字符才失配。失配之后 i 只前进一格j 归零于是前面已经确认匹配的那几个a全部白比了又要重新比一遍。主串里a越多浪费越严重最坏情况就是 O(n*m)。这里有个关键观察失配发生时我们已经知道主串当前位置之前的一段字符长什么样了因为那一段刚刚和模式串的前缀匹配过。暴力法把这个信息完全丢掉了KMP 的核心就是把这部分信息利用起来——既然主串那一段等于模式串的某个前缀那我能不能直接在模式串内部找一个更短的、同时是前缀又是后缀的部分把模式串指针挪过去主串指针不动这就是 KMP 的全部思想来源。理解到这一层后面 next 数组的求法就顺理成章了。2. next 数组的本质模式串的自我匹配很多人学 KMP 卡在 next 数组上是因为把它当成一个背下来的公式在记。其实 next 数组描述的是模式串自己的性质跟主串一点关系都没有。2.1 前缀与后缀的定义对模式串p的某个位置j表示p[0..j-1]这个子串我们找它最长的、相等的真前缀和真后缀的长度。真前缀指不包含最后一个字符的前缀真后缀指不包含第一个字符的后缀。举个例子模式串ababaca子串最长相等真前后缀长度a无0ab无0abaa1ababab2ababaaba3ababac无0ababacaa1这个长度序列0 0 1 2 3 0 1就是我们要的东西。它的含义是当在模式串第 j 个位置失配时说明p[0..j-1]已经和主串匹配上了而这段子串有一个长度为 k 的相等真前后缀那么我可以直接把模式串往前滑让它的前缀对齐到刚才那段后缀的位置从 k 继续比。因为那段后缀和前缀相等所以滑过去之后前缀部分天然就是匹配的不用再比。2.2 为什么主串指针不用回退这是 KMP 最反直觉也最精妙的地方。失配时我们移动的是模式串主串指针 i 一直往前走。原因在于任何可能匹配成功的起点都必须让模式串的前缀和主串某段后缀对齐而 next 数组给出的正是最长的那个可行对齐位置。比它更短的对齐要么已经被包含在内要么不可能成功。所以跳过中间那些起点是安全的不会漏掉正确答案。注意next 数组的求法有两种流派一种把 next[0] 设为 -1一种设为 0。两种都能跑通但边界处理不一样混用必出 bug。下面我统一用 next[0] 0 的版本逻辑更直观。3. 完整可编译的 C 实现直接上代码这份代码我在多个项目里用过边界情况都测过。#include iostream #include string #include vector using namespace std; // 求 next 数组next[i] 表示 p[0..i-1] 的最长相等真前后缀长度 vectorint buildNext(const string p) { int m p.size(); vectorint nxt(m, 0); // nxt[0] 恒为 0单个字符没有真前后缀 int k 0; // k 表示当前已匹配的前后缀长度 for (int i 1; i m; i) { // 失配时k 回退到上一个可能的前后缀长度 while (k 0 p[i] ! p[k]) { k nxt[k - 1]; } // 匹配成功前后缀长度加一 if (p[i] p[k]) { k; } nxt[i] k; } return nxt; } // KMP 主匹配返回第一次出现的下标找不到返回 -1 int kmpSearch(const string s, const string p) { if (p.empty()) return 0; int n s.size(), m p.size(); vectorint nxt buildNext(p); int j 0; // 模式串当前匹配到的位置 for (int i 0; i n; i) { while (j 0 s[i] ! p[j]) { j nxt[j - 1]; } if (s[i] p[j]) { j; } if (j m) { return i - m 1; // 匹配成功 } } return -1; } int main() { string s ababcabcacbab; string p abcac; int pos kmpSearch(s, p); cout match at: pos endl; // 输出 5 return 0; }编译命令很简单g -stdc11 -O2 kmp.cpp -o kmp ./kmp跑出来match at: 5和预期一致。这份代码里buildNext和kmpSearch的结构几乎一模一样这不是巧合——求 next 数组的过程本质上就是模式串自己和自己做 KMP 匹配。理解这一点代码就不用死记了。3.1 逐行拆解 buildNext 的回退逻辑buildNext里最容易看晕的是那个while循环。我们拿p ababaca走一遍i1p[1]bk0p[1]!p[0]不进 while也不进 ifnxt[1]0。i2p[2]ak0p[2]p[0]k 变 1nxt[2]1。i3p[3]bk1p[3]p[1]k 变 2nxt[3]2。i4p[4]ak2p[4]p[2]k 变 3nxt[4]3。i5p[5]ck3p[5]!p[3]进 whileknxt[2]1p[5]!p[1]继续knxt[0]0退出 whilep[5]!p[0]nxt[5]0。i6p[6]ak0p[6]p[0]k 变 1nxt[6]1。结果0 0 1 2 3 0 1和前面手算的完全对上。那个 while 循环的作用是当前后缀延伸失败时退而求其次找一个更短的、仍然满足相等前后缀的候选长度继续尝试。k nxt[k-1]这一步就是在已经匹配的前缀内部再找它的最长相等前后缀。3.2 匹配阶段的指针移动匹配阶段和求 next 阶段结构对称。主串指针 i 每次循环固定加一模式串指针 j 在失配时通过j nxt[j-1]回退。当 j 涨到 m 时说明整段匹配完成返回起点i - m 1。如果你要找出所有出现位置把return改成记录后j nxt[j-1]继续循环即可vectorint kmpSearchAll(const string s, const string p) { vectorint res; if (p.empty()) return res; int n s.size(), m p.size(); vectorint nxt buildNext(p); int j 0; for (int i 0; i n; i) { while (j 0 s[i] ! p[j]) j nxt[j - 1]; if (s[i] p[j]) j; if (j m) { res.push_back(i - m 1); j nxt[j - 1]; // 继续找下一个 } } return res; }4. 手写 KMP 时最容易翻车的几个地方代码看着短但坑是真不少。下面这几个是我和身边人实际踩过的列出来帮你省时间。4.1 next 数组下标越界的经典写法网上很多版本在 while 里写k nxt[k]而不是k nxt[k-1]。这种写法通常配套 next[0] -1 的约定如果你把两套约定混在一起轻则结果错误重则数组越界崩溃。判断标准很简单看 next[0] 是 0 还是 -1。是 0回退就用nxt[k-1]是 -1回退用nxt[k]并且 while 条件要写成k ! -1 ...。我建议新手统一用 next[0]0 这套边界更符合直觉。4.2 空模式串和空主串的处理p.empty()时数学上认为空串在任何位置都匹配返回 0 是合理约定。但如果你没加这个判断buildNext里vectorint nxt(0)是合法的可kmpSearch里p[j]会直接越界访问。这种 bug 在测试时如果只测正常串根本发现不了上线后遇到空输入就炸。养成习惯函数入口先处理空输入。4.3 用 int 存下标的溢出风险int在多数平台是 32 位能表示到约 21 亿。一般字符串够用但如果你处理的是超大文本比如几 GB 的日志文件一次性读进内存s.size()返回的是size_t赋给int会截断。稳妥做法是把所有下标类型统一成size_t或long long或者干脆用迭代器。我个人的习惯是匹配函数内部用int但在调用前断言s.size() INT_MAX。4.4 中文和 UTF-8 编码的字符边界KMP 是按字节比对的。如果你的字符串是 UTF-8 编码的中文一个汉字占 3 个字节按字节匹配虽然不会出错因为 UTF-8 是自同步编码不会出现半个字符误匹配但返回的下标是字节偏移不是字符位置。如果你需要按第几个汉字来定位得额外做一次字节到字符的映射。这个坑在做文本编辑器搜索功能时特别常见。坑点现象解决方式next 约定混用结果错误或越界统一 next[0]0回退用 nxt[k-1]空串未处理运行时崩溃入口判断 p.empty()int 截断超大串下标错误用 size_t 或加断言UTF-8 下标定位到半个汉字额外做字节到字符映射5. 从 next 到 nextval一次小优化标准 next 数组有个小缺陷。考虑模式串aaaabnext 是0 1 2 3 0。当在主串某个位置失配时比如p[3]a和主串字符不匹配我们回退到nxt[2]2也就是拿p[2]a再比一次。可p[2]和p[3]都是a既然p[3]都没匹配上p[2]必然也匹配不上这次回退是无效的。nextval 就是来解决这个的如果回退后的字符和当前字符相同就继续往前回退直到字符不同或到边界。vectorint buildNextval(const string p) { int m p.size(); vectorint nxt(m, 0); int k 0; for (int i 1; i m; i) { while (k 0 p[i] ! p[k]) k nxt[k - 1]; if (p[i] p[k]) k; // 关键优化如果回退位置字符相同直接继承更前面的值 if (k 0 p[i] p[k - 1]) { nxt[i] nxt[k - 1]; } else { nxt[i] k; } } return nxt; }对aaaabnextval 得到0 0 0 0 0失配时一步退到底省掉多次无效比较。在模式串重复字符多的场景下这个优化能明显减少比较次数。不过要注意nextval 只优化了回退后字符相同这一种情况对一般串提升有限属于锦上添花。6. 实测性能对比与适用边界光说理论不够我拿几组数据实测了一下。测试环境是普通笔记本编译开 -O2主串用随机生成的字符模式串分别用随机串和高度重复串。场景主串长度模式串暴力法耗时KMP 耗时随机串100万长度10随机约 12ms约 18ms重复串100万aaaa...ab约 850ms约 15ms无匹配100万长度100随机约 95ms约 20ms可以看到在随机串上 KMP 反而不一定比暴力法快因为 KMP 多了一次 O(m) 的预处理而且随机串下失配发生得早暴力法回退的代价不大。KMP 的优势在模式串有大量重复前缀、或者主串和模式串高度相似时才会体现出来比如上面那个aaaa...ab的场景暴力法慢了五十多倍。所以选型建议是模式串短比如小于 10、主串随机暴力法足够代码还简单。模式串有重复结构、或需要保证最坏情况性能上 KMP。需要多模式匹配一次找多个关键词KMP 不合适应该用 AC 自动机。实际工程中做文本搜索直接用标准库的string::find它内部实现通常已经足够优化除非你有特殊需求。提示不要为了用 KMP 而用 KMP。我见过有人在只需要匹配一次、模式串只有三五个字符的场景硬上 KMP代码复杂度上去了性能没提升维护成本还高。工具要匹配场景。7. 把 KMP 思想迁移到其他问题KMP 的 next 数组思想其实可以迁移到不少地方这也是它值得深入理解的原因。一个是最短循环节问题。如果字符串长度 n 能被n - nxt[n-1]整除那么n - nxt[n-1]就是它的最短循环节长度。比如abcabcabcnxt 最后一位是 6n-63正好是循环节abc的长度。这个结论在做字符串压缩、周期检测时很有用。另一个是判断一个串是否是另一个串的重复拼接。把两个串拼起来看模式串在其中的匹配位置如果匹配位置不是 0 也不是长度本身就说明存在周期性。还有一个是回文串相关的处理。把原串和它的反转串做 KMP可以求最长回文前缀之类的问题。这些迁移用法在算法题里出现频率不低理解了 next 的本质这些变形都是顺手的。我在实际写代码时的体会是KMP 真正难的不是代码而是建立用已匹配信息避免重复比较这个思维习惯。一旦这个思维建立起来你会发现很多看似需要暴力枚举的问题都能找到类似的优化切入点。next 数组的求法我建议至少手推三遍推到不用看代码就能写出k nxt[k-1]这一步才算真的掌握了。