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++免费学习笔记（深入）”；
用 i 遍历主串，j 遍历模式串如果主串字符与模式串字符相等，i 和 j 同时后移如果不等且 j > 0，则 j 回退到 next[j – 1]如果不等且 j == 0，则仅 i++当 j 达到模式串长度时，说明找到一次匹配，记录起始位置，并可选择继续搜索
C++代码实现示例
#include #include #includestd::vector buildNext(const std::string& pattern) {int n = pattern.length();std::vector next(n, 0);int j = 0;for (int i = 1; i 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 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 << "Pattern found at index " << pos << std::endl;}return 0;
}
上述代码中，buildNext函数生成next数组，kmpSearch函数返回所有匹配位置。时间复杂度为O(m+n)，空间复杂度O(n)，适合处理长文本中的高效模式匹配。
基本上就这些。掌握next数组的构造逻辑和匹配过程中的状态转移，就能灵活应用KMP算法解决实际问题。
以上就是c++++中如何实现KMP算法_c++ KMP算法实现方法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1479421.html
微信扫一扫 
支付宝扫一扫 
