KMP算法通过构建next数组实现高效字符串匹配，先预处理模式串得到最长相等前后缀信息，再利用该表在主串中跳过无效比较，最终在O(m+n)时间内完成匹配。
在C++中实现KMP（Knuth-Morris-Pratt）算法，核心是通过预处理模式串生成一个部分匹配表（通常称为next数组），利用该表在匹配失败时跳过不必要的比较，从而提高字符串匹配效率。整个过程分为两步：构建next数组、进行主串与模式串的匹配。
构建next数组（失配函数）
next数组记录模式串每个位置之前的最长相等前后缀长度。这个信息用于在匹配失败时决定模式串应向右滑动多少位。
具体做法是从左到右遍历模式串，使用两个指针 i 和 j，其中 j 表示当前最长前缀的长度：
- 初始化 next[0] = 0，j = 0
- 从 i = 1 开始遍历模式串
- 如果 pattern[i] == pattern[j]，则 next[i] = ++j，i++
- 否则若 j > 0，则回退 j = next[j - 1]，继续比较
- 若 j == 0，则 next[i] = 0，i++
执行KMP匹配过程
使用构建好的next数组，在主串中查找模式串出现的位置。同样使用双指针技术：
立即学习“C++免费学习笔记（深入）”；
C编写，实现字符串摘要、文件摘要两个功能。里面主要包含3个文件: Md5.cpp、Md5.h、Main.cpp。其中Md5.cpp是算法的代码，里的代码大多是从 rfc-1321 里copy过来的；Main.cpp是主程序。
- 用 i 遍历主串，j 遍历模式串
- 如果主串字符与模式串字符相等，i 和 j 同时后移
- 如果不等且 j > 0，则 j 回退到 next[j - 1]
- 如果不等且 j == 0，则仅 i++
- 当 j 达到模式串长度时，说明找到一次匹配，记录起始位置，并可选择继续搜索
C++代码实现示例
#include#include #include std::vector
buildNext(const std::string& pattern) { int n = pattern.length(); std::vector next(n, 0); int j = 0; for (int i = 1; i < n; ++i) { while (j > 0 && pattern[i] != pattern[j]) { j = next[j - 1]; } if (pattern[i] == pattern[j]) { ++j; } next[i] = j; } return next; } std::vector
kmpSearch(const std::string& text, const std::string& pattern) { std::vector matches; if (pattern.empty()) return matches; auto next = buildNext(pattern); int m = text.length(); int n = pattern.length(); int j = 0; for (int i = 0; i zuojiankuohaophpcn m; ++i) { while (j > 0 && text[i] != pattern[j]) { j = next[j - 1]; } if (text[i] == pattern[j]) { ++j; } if (j == n) { matches.push_back(i - n + 1); j = next[j - 1]; // 准备下一次匹配 } } return matches;}
int main() { std::string text = "ABABDABACDABABCABC"; std::string pattern = "ABABCAB"; auto result = kmpSearch(text, pattern);
for (int pos : result) { std::cout zuojiankuohaophpcnzuojiankuohaophpcn "Pattern found at index " zuojiankuohaophpcnzuojiankuohaophpcn pos zuojiankuohaophpcnzuojiankuohaophpcn std::endl; } return 0;}
上述代码中，buildNext函数生成next数组，kmpSearch函数返回所有匹配位置。时间复杂度为O(m+n)，空间复杂度O(n)，适合处理长文本中的高效模式匹配。
基本上就这些。掌握next数组的构造逻辑和匹配过程中的状态转移，就能灵活应用KMP算法解决实际问题。
