KMP算法通过next数组实现主串指针不回退，利用模式串最长公共前后缀信息跳过重复比较，将匹配复杂度降至O(m+n)；核心是构建next数组，即对模式串自匹配求每个位置前缀函数值，再用该数组在文本串中滑动匹配，避免暴力回溯。
在C++中实现KMP（Knuth-Morris-Pratt）算法，核心在于利用模式串的“部分匹配表”（即next数组），避免在字符串匹配过程中重复比较已知相同的字符。相比暴力匹配，KMP将时间复杂度从O(mn)优化到O(m+n)，适合处理长文本的精确匹配问题。
理解KMP的核心思想
KMP算法的关键是当主串和模式串在某个位置失配时，不回退主串的指针，而是通过预处理模式串得到的next数组，将模式串向右“滑动”到下一个可能匹配的位置。
重点在于：
主串指针不回退模式串根据最长公共前后缀移动next[i] 表示模式串前i个字符中最长相等前后缀的长度
构建next数组（失败函数）
next数组的构造本质上是一个“模式串自匹配”的过程。我们用两个指针i和j，其中j表示当前最长前缀的长度，i遍历模式串。
立即学习“C++免费学习笔记（深入）”；
代码示例：
void buildNext(const string& pattern, vector& next) { int n = pattern.length(); next[0] = 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; }}
说明：当pattern[i] != pattern[j]时，j回退到next[j-1]，直到匹配或j为0。
执行KMP字符串匹配
使用构建好的next数组，在主串中查找所有模式串出现的位置。
完整匹配函数：
vector kmpSearch(const string& text, const string& pattern) { vector result; if (pattern.empty()) return result;vector next(pattern.length());buildNext(pattern, next);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) { result.push_back(i - n + 1); j = next[j - 1]; // 继续找下一个匹配 }}return result;
}
该函数返回所有匹配起始下标的列表。例如在"ABABDABACDABABCABC"中查找"ABABCAB"，会返回对应的索引位置。
测试与使用示例
简单调用方式：
int main() { string text = "ABABDABACDABABCABC"; string pattern = "ABABCAB"; vector matches = kmpSearch(text, pattern);for (int pos : matches) { cout << "匹配位置: " << pos << endl;}return 0;
}
输出结果会显示所有成功匹配的起始索引。
基本上就这些。KMP难点在next数组的理解和构造，一旦掌握，代码其实很简洁。关键是明白为什么能跳过某些比较——因为利用了前缀信息，避免重复劳动。
以上就是C++怎么实现KMP算法_C++字符串匹配算法与KMP实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1483381.html
微信扫一扫 
支付宝扫一扫 
