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数组，在主串中查找模式串出现的位置。同样使用双指针技术：
立即学习“”；
- 用 i 遍历主串，j 遍历模式串
- 如果主串字符与模式串字符相等，i 和 j 同时后移
- 如果不等且 j > 0，则 j 回退到 next[j – 1]
- 如果不等且 j == 0，则仅 i++
- 当 j 达到模式串长度时，说明找到一次匹配，记录起始位置，并可选择继续搜索
C++代码实现示例
#include <iostream> #include <vector> #include <string> <p>std::vector<int> buildNext(const std::string& pattern) { int n = pattern.length(); std::vector<int> 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; }</p><p>std::vector<int> kmpSearch(const std::string& text, const std::string& pattern) { std::vector<int> matches; if (pattern.empty()) return matches;</p><pre class='brush:php;toolbar:false;'>auto next = buildNext(pattern); int m = text.length(); int n = pattern.length(); int j = 0; for (int i = 0; i < 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;
登录后复制
}
法语助手旗下的AI智能写作平台，支持语法、拼写自动纠错，一键改写、润色你的法语作文。
31 int mn() { std::string text = “ABABDABACDABABCABC”; std::string pattern = “ABABCAB”; auto result = kmpSearch(text, pattern);
for (int pos : result) { std::cout << "Pattern found at index " << pos << std::endl; } return 0;
登录后复制
}
上述代码中，buildNext函数生成next数组，kmpSearch函数返回所有匹配位置。时间复杂度为O(m+n)，空间复杂度O(n)，适合处理长文本中的高效模式匹配。
基本上就这些。掌握next数组的构造逻辑和匹配过程中的状态转移，就能灵活应用KMP算法解决实际问题。
以上就是++中如何实现KMP算法_c++ KMP算法实现方法的详细内容，更多请关注php中文网其它相关文章！
相关标签：
微信扫一扫打赏
支付宝扫一扫打赏
