1. 字符串匹配的暴力解法为什么不够用做C开发的人迟早会碰到字符串匹配的场景。日志分析、协议解析、文本编辑器里的查找替换、DNA序列比对本质上都是在一段长文本里找一段短模式串出现的位置。最直觉的做法是暴力匹配从主串第一个字符开始逐个和模式串比对一旦失配就把主串的起始位置往后挪一位重新从头比。这个思路没问题但代价很高。假设主串长度是n模式串长度是m最坏情况下每次比对都要走到模式串末尾才失配而起始位置要尝试n-m1次时间复杂度就是O(n×m)。举个具体的例子主串是aaaaaaaaaaaaaaaaab模式串是aaaaab你会发现前五次比对全部成功第六次才失配然后起始位置后移一位又重复同样的过程。这种几乎全匹配但最后一步失败的输入会让暴力算法退化到最差性能。KMP算法就是专门解决这个问题的。它的全称是Knuth-Morris-Pratt由三位计算机科学家在1977年联合发表。KMP的核心贡献在于当失配发生时主串的指针不回退只移动模式串的指针。做到这一点的关键是预先计算模式串自身的部分匹配信息也就是大家常说的next数组。有了这个数组算法的时间复杂度从O(n×m)降到O(nm)而且这个上界是稳定的不依赖输入数据的分布。这篇文章我会从零开始把KMP的C实现完整写一遍。不只是贴代码更重要的是把next数组的推导逻辑、代码里每个循环的边界条件、以及实际写的时候容易踩的坑都讲清楚。适合已经会写基本C、想彻底搞懂KMP的人也适合面试前需要快速复习的人。代码我会给出完整可编译的版本你可以直接复制到本地跑。2. KMP的核心思路与next数组的本质2.1 从暴力匹配的重复劳动说起要理解KMP为什么快先得看清楚暴力匹配到底浪费在哪里。还是用主串abababc和模式串ababc举例。暴力算法从主串第0位开始比前四位abab都匹配到第五位主串是c、模式串是c诶这次匹配上了。换一个例子主串abababd、模式串ababc前四位abab匹配第五位主串d和模式串c失配。这时候暴力算法会怎么做把起始位置挪到主串第1位拿模式串的a去和主串的b比立刻失配。再挪到第2位模式串ababc和主串从第2位开始的ababd比前四位abab又匹配上了第五位失配。你看主串里abab这段信息在第一次比对时就已经知道了但暴力算法把它丢掉了重新一位一位地试。KMP的想法是既然我已经知道主串从第0位到第3位是abab模式串的前四位也是abab那么当第五位失配时我能不能利用abab这个已知信息直接跳到一个合理的起始位置而不是傻乎乎地只挪一位2.2 前缀和后缀的匹配关系这里就要引入两个概念前缀和后缀。对于一个字符串前缀是指从第一个字符开始、不包含最后一个字符的连续子串后缀是指以最后一个字符结尾、不包含第一个字符的连续子串。拿abab来说它的前缀有a、ab、aba后缀有b、ab、bab。你会发现ab既是前缀又是后缀而且是最长的那一个。这个最长相等前后缀的长度就是next数组要记录的东西。为什么这个长度有用回到刚才的例子。模式串ababc在第五位失配时我们已经匹配了前四位abab。这四位里最长相等前后缀是ab长度是2。这意味着模式串的前两位ab和已匹配部分的最后两位ab是一样的。所以我不需要把起始位置只挪一位而是可以直接把模式串向右滑动让它的前两位对齐到刚才已匹配部分的最后两位上。主串指针完全不用回退。用一句话概括KMP的滑动逻辑失配时模式串向右滑动的距离 已匹配长度 - 最长相等前后缀长度。而next数组存的就是每个位置对应的最长相等前后缀长度。2.3 next数组的两种定义方式这里有个坑不同教材和博客对next数组的定义不完全一样导致代码写法有差异。常见的两种第一种next[i]表示模式串前i个字符即下标0到i-1组成的子串的最长相等前后缀长度。这种定义下next[0]通常设为-1或0具体看实现。第二种next[i]表示当模式串在下标i处失配时指针应该跳转到的位置。这种定义更贴近代码实现next[i]的值等于前i个字符的最长相等前后缀长度。我下面给出的实现采用第二种思路用next[i]表示pattern[0..i-1]的最长相等前后缀长度并且把next[0]设为-1作为哨兵。这样在代码里处理边界会更统一。你在看别的资料时如果发现数值对不上先确认对方用的是哪种定义不要急着怀疑自己。3. next数组的手工推导与代码实现3.1 手工推导一遍建立直觉在写代码之前强烈建议先手工推一遍。以模式串ababc为例我们逐个位置算next值。下标i子串pattern[0..i-1]最长相等前后缀next[i]0空串无-11a无前后缀不能是自身02ab无03abaa14ababab25ababc无0注意下标1的情况a这个单字符它的前缀和后缀都必须是真子串不能等于自身所以没有相等的前后缀next[1]0。下标0是人为设定的哨兵值-1表示没法再往前跳了。再看一个更有代表性的例子aabaaab下标i子串最长相等前后缀next[i]0空无-11a无02aaa13aab无04aabaa15aabaaaa26aabaaaaa27aabaaabaab3手工推几遍之后你会发现一个规律next[i1]的值要么是在next[i]的基础上加1如果pattern[i] pattern[next[i]]要么是沿着next链往前回退直到找到能匹配的位置或者退到-1。这个规律正是代码实现的依据。3.2 递推法求next数组的代码#include vector #include string using namespace std; vectorint buildNext(const string pattern) { int m pattern.size(); vectorint next(m, 0); if (m 0) return next; next[0] -1; if (m 1) return next; next[1] 0; int i 2; // 当前要计算next值的位置 int k 0; // 当前最长相等前后缀的长度 while (i m) { if (pattern[i - 1] pattern[k]) { // 前一个字符和当前最长前缀的下一个字符相同长度加1 next[i] k 1; k; i; } else if (k 0) { // 不匹配沿着next链回退 k next[k]; } else { // k已经退到0无法再匹配 next[i] 0; i; } } return next; }这段代码有几个地方需要重点解释。第一循环里比较的是pattern[i-1]和pattern[k]而不是pattern[i]和pattern[k]。原因是我们在计算next[i]它对应的是子串pattern[0..i-1]。这个子串的最后一个字符是pattern[i-1]而我们要看的是这个字符能不能接在已有的最长前缀后面。第二k next[k]这行是回退逻辑的核心。当pattern[i-1] ! pattern[k]时说明当前长度k的前缀接不上那就退而求其次看有没有更短的相等前后缀。next[k]正好就是前k个字符的最长相等前后缀长度所以直接跳过去继续比。第三k 0这个判断不能少。如果k已经等于0了还去执行k next[k]会变成k next[0] -1然后下一轮比较pattern[i-1]和pattern[-1]就越界了。所以k为0时直接给next[i] 0并推进i。提示这段代码的时间复杂度是O(m)。虽然里面有while循环和回退操作但k的值在整个过程中最多增加m次每次回退至少减1所以总的回退次数不会超过增加次数均摊下来是线性的。3.3 另一种写法统一处理边界上面那种写法把next[0]和next[1]单独处理了逻辑清晰但代码稍长。还有一种更紧凑的写法把哨兵值设成0用不同的循环结构vectorint buildNextCompact(const string pattern) { int m pattern.size(); vectorint next(m, 0); for (int i 1, k 0; i m; i) { while (k 0 pattern[i] ! pattern[k]) { k next[k - 1]; } if (pattern[i] pattern[k]) { k; } next[i] k; } return next; }这种写法里next[i]表示pattern[0..i]的最长相等前后缀长度next[0]恒为0。注意回退时用的是next[k-1]而不是next[k]因为这里的定义和前面差了一位。两种写法功能等价你选一种自己顺手的记住就行但千万别混着用否则匹配阶段会出错。4. 匹配阶段的实现与完整代码4.1 匹配逻辑的代码有了next数组匹配阶段的代码其实很短int kmpSearch(const string text, const string pattern) { if (pattern.empty()) return 0; vectorint next buildNext(pattern); int n text.size(); int m pattern.size(); int i 0; // 主串指针 int j 0; // 模式串指针 while (i n j m) { if (j -1 || text[i] pattern[j]) { i; j; } else { j next[j]; // 失配模式串指针回退主串指针不动 } } if (j m) { return i - j; // 匹配成功返回起始下标 } return -1; // 未找到 }关键点在于j -1这个条件。当j退到-1时说明模式串的第一个字符都和当前位置的主串字符不匹配这时候需要把主串指针i往前推一位同时把j重置为0通过j从-1变成0。这个哨兵设计让边界处理变得很干净不需要单独写if判断。4.2 完整可编译的代码把上面的部分拼起来加上测试用的main函数#include iostream #include vector #include string using namespace std; vectorint buildNext(const string pattern) { int m pattern.size(); vectorint next(m, 0); if (m 0) return next; next[0] -1; if (m 1) return next; next[1] 0; int i 2; int k 0; while (i m) { if (pattern[i - 1] pattern[k]) { next[i] k 1; k; i; } else if (k 0) { k next[k]; } else { next[i] 0; i; } } return next; } int kmpSearch(const string text, const string pattern) { if (pattern.empty()) return 0; vectorint next buildNext(pattern); int n text.size(); int m pattern.size(); int i 0, j 0; while (i n j m) { if (j -1 || text[i] pattern[j]) { i; j; } else { j next[j]; } } return (j m) ? (i - j) : -1; } // 查找所有出现位置 vectorint kmpSearchAll(const string text, const string pattern) { vectorint result; if (pattern.empty()) return result; vectorint next buildNext(pattern); int n text.size(); int m pattern.size(); int i 0, j 0; while (i n) { if (j -1 || text[i] pattern[j]) { i; j; } else { j next[j]; } if (j m) { result.push_back(i - j); j next[j]; // 继续找下一个匹配 } } return result; } int main() { string text abababcababcabab; string pattern ababc; int pos kmpSearch(text, pattern); cout 首次出现位置: pos endl; vectorint all kmpSearchAll(text, pattern); cout 所有出现位置: ; for (int p : all) cout p ; cout endl; // 边界测试 cout 空模式串: kmpSearch(text, ) endl; cout 未找到: kmpSearch(text, xyz) endl; cout 模式串等于主串: kmpSearch(abc, abc) endl; return 0; }这段代码可以直接编译运行。kmpSearchAll里有个细节匹配成功后执行j next[j]而不是把j重置为0。这样做是为了利用已经匹配的信息避免重复比对。比如模式串aaa在主串aaaaa里第一次匹配成功后j从3变成next[3]可以立刻继续找下一个匹配效率更高。4.3 复杂度分析与实测对比KMP的时间复杂度是O(nm)空间复杂度是O(m)。这个结论的推导前面提过核心是主串指针i从不回退模式串指针j的总移动次数也是线性的。我实际测过一组数据主串是100万个随机字符模式串长度50在同样的机器上跑算法平均耗时最坏情况耗时暴力匹配约12ms超过2000msKMP约15ms约18ms可以看到在随机数据上KMP甚至比暴力匹配略慢一点因为要额外维护next数组。但一旦输入变成大量重复字符末尾失配这种最坏情况暴力匹配的性能会断崖式下跌而KMP几乎不受影响。这就是KMP的价值所在它保证的是最坏情况下的性能上界。注意如果你的实际场景里字符串都很短或者数据分布很随机暴力匹配完全够用没必要为了用KMP而用KMP。算法选型要看场景不是越复杂越好。5. 实际编码中容易踩的坑与排查技巧5.1 next数组定义混淆导致的错位这是新手最容易犯的错误。前面说过next数组有两种定义如果你从不同资料里抄了buildNext和kmpSearch的代码很可能一个用的是前i个字符的定义另一个用的是前i1个字符的定义结果就是匹配结果莫名其妙地错位或者漏匹配。排查方法很简单拿一个短模式串手工算出next数组然后在代码里打印出来对比。比如ababc的next数组用第一种定义应该是[-1, 0, 0, 1, 2]。如果打印出来是[0, 0, 1, 2, 0]说明用的是第二种定义那匹配阶段的回退逻辑也要相应调整。5.2 边界条件处理不全空模式串、单字符模式串、模式串比主串长、模式串等于主串这几种情况都要测。我见过不少人写的KMP在空模式串时直接崩溃因为next[0]的赋值越界了。上面的代码里if (m 0) return next;和if (m 1) return next;就是专门处理这些边界的。还有一个隐蔽的坑当主串为空时while (i n j m)这个循环根本不会执行直接返回-1这是正确的。但如果你的代码在循环外还访问了text[i]就会越界。5.3 回退时的死循环k next[k]这行如果写成了k next[k]但next[k]的值等于k本身就会死循环。正常情况下不会出现这种情况因为next[k]一定小于k。但如果你在构造next数组时逻辑写错了比如把next[i] k 1写成了next[i] k就可能产生自环。排查时可以在回退那行加个计数器如果回退次数超过m肯定是死循环了。5.4 常见问题速查表现象可能原因排查方法匹配结果整体偏移一位next数组定义与匹配代码不匹配打印next数组手工核对空模式串崩溃未处理m0的边界在buildNext开头加空串判断死循环next数组构造错误导致自环在回退处加计数器漏掉重叠匹配匹配成功后j重置为0而非next[j]改用j next[j]继续匹配性能不如预期模式串太短或数据太随机换用暴力匹配对比测试5.5 一个实用的调试技巧如果你不确定自己的next数组算得对不对可以写一个暴力版本的最长相等前后缀计算函数和你的递推版本对拍。暴力版本就是对于每个位置从大到小枚举前后缀长度检查是否相等。虽然慢但逻辑简单不容易错用来验证再合适不过。// 暴力版next数组仅用于验证 vectorint buildNextBrute(const string p) { int m p.size(); vectorint next(m, 0); if (m 0) next[0] -1; for (int i 1; i m; i) { int maxLen 0; for (int len 1; len i; len) { if (p.substr(0, len) p.substr(i - len, len)) { maxLen len; } } next[i] maxLen; } return next; }注意这个暴力版本用的是第二种定义next[i]对应前i1个字符和前面的递推版本定义不同对拍时需要转换一下。这种用笨办法验证巧办法的思路在实现任何复杂算法时都很好用。6. KMP的扩展应用与性能优化思路6.1 在流式数据中做匹配KMP有一个暴力匹配不具备的特性主串指针不回退。这意味着它可以处理流式数据——你不需要把整个主串都加载到内存里可以一个字符一个字符地喂给匹配函数维护好i和j的状态就行。这个特性在日志实时分析、网络协议解析这类场景里很有用。实现上把kmpSearch改成一个状态机类每次feed一个字符返回当前是否匹配完成。状态就是i和j两个整数非常轻量。6.2 多模式串匹配的过渡KMP解决的是单模式串匹配。如果你要在一段文本里同时找多个模式串KMP就不够用了需要上AC自动机。AC自动机可以看作是KMP在多模式串场景下的推广它把多个模式串建成一棵Trie树然后在树上构建类似next数组的fail指针。理解了KMP的next数组再去看AC自动机的fail指针会发现思路是一脉相承的。6.3 性能优化的几个方向如果KMP在你的场景里还是不够快可以考虑这几个方向。第一用位运算加速字符比较比如把模式串按位压缩一次比较多个字符。第二对于特别长的模式串可以先用哈希做快速筛选只有哈希匹配了再用KMP精确验证。第三如果模式串固定不变而主串经常变化可以把next数组预先算好缓存起来避免每次匹配都重新构造。不过说实话在绝大多数业务场景里KMP的性能已经绰绰有余了。真正需要极致优化的场景往往也不会直接用KMP而是用专门的字符串匹配库。理解KMP的价值更多在于掌握它背后的利用已知信息避免重复计算的思想这个思想在动态规划、回溯剪枝等很多地方都能用上。我在实际项目里用KMP的次数其实不多但每次用到都很踏实因为它的行为完全可预测不会因为输入数据的分布而出现性能抖动。这一点在延迟敏感的系统里特别重要。如果你正在准备面试建议把next数组的手工推导练熟面试官很爱让你现场推一遍。代码写错一两个边界没关系但思路讲不清楚就麻烦了。