企业官网建设流程全解析

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

做C++开发的人迟早会碰到字符串匹配的场景。日志分析、协议解析、文本编辑器里的查找替换、DNA序列比对，本质上都是在一段长文本里找一段短模式串出现的位置。最直觉的做法是暴力匹配：从主串第一个字符开始，逐个和模式串比对，一旦失配就把主串的起始位置往后挪一位，重新从头比。

这个思路没问题，但代价很高。假设主串长度是n，模式串长度是m，最坏情况下每次比对都要走到模式串末尾才失配，而起始位置要尝试n-m+1次，时间复杂度就是O(n×m)。举个具体的例子，主串是"aaaaaaaaaaaaaaaaab"，模式串是"aaaaab"，你会发现前五次比对全部成功，第六次才失配，然后起始位置后移一位，又重复同样的过程。这种"几乎全匹配但最后一步失败"的输入，会让暴力算法退化到最差性能。

KMP算法就是专门解决这个问题的。它的全称是Knuth-Morris-Pratt，由三位计算机科学家在1977年联合发表。KMP的核心贡献在于：当失配发生时，主串的指针不回退，只移动模式串的指针。做到这一点的关键，是预先计算模式串自身的"部分匹配信息"，也就是大家常说的next数组。有了这个数组，算法的时间复杂度从O(n×m)降到O(n+m)，而且这个上界是稳定的，不依赖输入数据的分布。

这篇文章我会从零开始，把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值。

注意下标1的情况，"a"这个单字符，它的前缀和后缀都必须是真子串（不能等于自身），所以没有相等的前后缀，next[1]=0。下标0是人为设定的哨兵值-1，表示"没法再往前跳了"。

再看一个更有代表性的例子"aabaaab"：

手工推几遍之后，你会发现一个规律：next[i+1]的值，要么是在next[i]的基础上加1（如果pattern[i] == pattern[next[i]]），要么是沿着next链往前回退，直到找到能匹配的位置或者退到-1。这个规律正是代码实现的依据。

3.2 递推法求next数组的代码

#include <vector> #include <string> using namespace std; vector<int> buildNext(const string& pattern) { int m = pattern.size(); vector<int> 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，用不同的循环结构：

vector<int> buildNextCompact(const string& pattern) { int m = pattern.size(); vector<int> 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; vector<int> 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; vector<int> buildNext(const string& pattern) { int m = pattern.size(); vector<int> 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; vector<int> 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; } // 查找所有出现位置 vector<int> kmpSearchAll(const string& text, const string& pattern) { vector<int> result; if (pattern.empty()) return result; vector<int> 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; vector<int> 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(n+m)，空间复杂度是O(m)。这个结论的推导前面提过，核心是主串指针i从不回退，模式串指针j的总移动次数也是线性的。

我实际测过一组数据，主串是100万个随机字符，模式串长度50，在同样的机器上跑：

可以看到，在随机数据上KMP甚至比暴力匹配略慢一点，因为要额外维护next数组。但一旦输入变成"大量重复字符+末尾失配"这种最坏情况，暴力匹配的性能会断崖式下跌，而KMP几乎不受影响。这就是KMP的价值所在：它保证的是最坏情况下的性能上界。

注意：如果你的实际场景里字符串都很短，或者数据分布很随机，暴力匹配完全够用，没必要为了用KMP而用KMP。算法选型要看场景，不是越复杂越好。

5. 实际编码中容易踩的坑与排查技巧

5.1 next数组定义混淆导致的错位

这是新手最容易犯的错误。前面说过next数组有两种定义，如果你从不同资料里抄了buildNext和kmpSearch的代码，很可能一个用的是"前i个字符"的定义，另一个用的是"前i+1个字符"的定义，结果就是匹配结果莫名其妙地错位或者漏匹配。

排查方法很简单：拿一个短模式串，手工算出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 常见问题速查表

5.5 一个实用的调试技巧

如果你不确定自己的next数组算得对不对，可以写一个暴力版本的最长相等前后缀计算函数，和你的递推版本对拍。暴力版本就是对于每个位置，从大到小枚举前后缀长度，检查是否相等。虽然慢，但逻辑简单不容易错，用来验证再合适不过。

// 暴力版next数组，仅用于验证 vector<int> buildNextBrute(const string& p) { int m = p.size(); vector<int> 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]对应前i+1个字符），和前面的递推版本定义不同，对拍时需要转换一下。这种"用笨办法验证巧办法"的思路，在实现任何复杂算法时都很好用。

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数组的手工推导练熟，面试官很爱让你现场推一遍。代码写错一两个边界没关系，但思路讲不清楚就麻烦了。