KMP算法通过构建next数组避免主串指针回退，在O(n+m)时间内完成字符串匹配，核心是利用模式串的最长相等前后缀信息进行跳转，实现高效搜索。
KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，能在 O(n + m) 时间内找出模式串在主串中的位置，避免了暴力匹配中不必要的回溯。下面详细讲解其原理并给出 C++ 实现。
核心思想：利用已匹配部分的信息
在暴力匹配中，一旦失配，主串指针会回退，导致重复比较。KMP 的关键是 不回退主串指针，而是根据模式串的结构，移动模式串，跳过不可能匹配的位置。
实现这一点的核心是构建一个叫做 next 数组（也叫失效函数或部分匹配表），记录模式串每个位置前最长的相等前缀和后缀长度。
next 数组的构造
next[i] 表示模式串从 0 到 i 这一段中，最长的相等真前缀与真后缀的长度。
立即学习“C++免费学习笔记（深入）”；
例如模式串 “ABABC”：
“A” → 0″AB” → 0″ABA” → 1 (“A”)”ABAB” → 2 (“AB”)”ABABC” → 0
构造过程类似 KMP 匹配，用两个指针 j 和 i，j 表示当前最长前缀的下一个位置，i 遍历模式串。
// 构建 next 数组vector buildNext(const string& pat) {int m = pat.length();vector next(m, 0);int j = 0; // 最长相等前后缀的长度for (int i = 1; i 0 && pat[i] != pat[j]) {j = next[j – 1];}if (pat[i] == pat[j]) {j++;}next[i] = j;}return next;}
KMP 主匹配过程
使用 next 数组，在主串中逐个比较字符。当发生失配时，模式串指针回退到 next[j-1] 的位置，而不是从头开始。
int kmpSearch(const string& text, const string& pattern) { if (pattern.empty()) return 0; vector next = buildNext(pattern); int n = text.length(); int m = 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 == m) { return i - m + 1; // 找到匹配，返回起始下标 }}return -1; // 未找到
}
完整可运行示例
#include iostream>#include #include using namespace std;
vector buildNext(const string& pat) {int m = pat.length();vector next(m, 0);int j = 0;for (int i = 1; i 0 && pat[i] != pat[j]) {j = next[j – 1];}if (pat[i] == pat[j]) {j++;}next[i] = j;}return next;}
int kmpSearch(const string& text, const string& pattern) {if (pattern.empty()) return 0;vector next = buildNext(pattern);int n = text.length();int m = 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 == m) { return i - m + 1; }}return -1;
}
int main() {string text = “ABABDABACDABABCABC”;string pattern = “ABABC”;int pos = kmpSearch(text, pattern);if (pos != -1) {cout
基本上就这些。理解 next 数组的含义和构造方式是掌握 KMP 的关键。代码不复杂但容易忽略细节，比如 while 循环中的回退逻辑。多调试几个例子有助于加深理解。
以上就是c++++怎么实现一个高效的字符串匹配算法(KMP)_c++ KMP算法实现与原理讲解的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1480690.html
微信扫一扫 
支付宝扫一扫 
