KMP算法通过构建next数组避免回溯，实现O(n+m)字符串匹配。首先用双指针法构造模式串的最长相等前后缀数组，再利用该数组在主串中滑动匹配，失配时根据next跳转，最终找出所有匹配位置。
KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配方法，能在O(n + m)时间内完成模式串在主串中的查找，避免了暴力匹配中不必要的回溯。下面介绍C++中如何实现KMP算法。
1. 理解KMP的核心思想
KMP的关键在于预处理模式串，构建一个next数组（也叫失配函数或部分匹配表），记录每个位置前缀和后缀的最长公共长度。当匹配失败时，利用next数组决定模式串应该向右滑动多少位，而不是从头开始比较。
例如，模式串 “ABABC” 的 next 数组为 [0, 0, 1, 2, 0]。
2. 构建next数组
next[i] 表示模式串前 i+1 个字符中，最长相等前后缀的长度（不包含整个子串本身）。构造过程类似双指针：
立即学习“C++免费学习笔记（深入）”；
用 j 表示当前最长前缀的长度，初始为 0i 从 1 开始遍历模式串，若 pattern[i] == pattern[j]，则 next[i] = ++j如果不等且 j > 0，则回退 j = next[j – 1]，继续比较直到 j=0 或匹配成功为止
代码如下：
vector buildNext(const string& pattern) { int m = pattern.size(); vector next(m, 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;}
3. 执行KMP搜索
使用构建好的next数组，在主串中滑动匹配：
用 i 遍历主串，j 表示模式串当前匹配位置如果字符相等，i 和 j 同时前进如果不等且 j > 0，j 回退到 next[j-1]如果 j=0 仍不匹配，只移动 i当 j 达到模式串长度时，说明找到一次匹配
完整搜索函数：
vector kmpSearch(const string& text, const string& pattern) { vector matches; if (pattern.empty()) return matches;vector next = buildNext(pattern);int n = text.size(), m = pattern.size();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 == m) { matches.push_back(i - m + 1); j = next[j - 1]; // 准备下一次匹配 }}return matches;
}
4. 使用示例
测试代码：
#include #include using namespace std;int main() {string text = "ABABDABACDABABCABC";string pattern = "ABABC";
vector result = kmpSearch(text, pattern);cout << "Pattern found at positions: ";for (int pos : result) { cout << pos << " ";}cout << endl;return 0;
}
输出：Pattern found at positions: 8
基本上就这些。KMP算法难点在next数组的理解与构造，一旦掌握，就能高效处理大规模文本匹配问题。
以上就是c++++怎么实现KMP字符串匹配算法_c++高效字符串匹配KMP算法实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1483385.html
微信扫一扫 
支付宝扫一扫 
