KMP算法通过构建next数组优化字符串匹配，避免主串指针回溯。1. next数组记录模式串各位置最长相等前后缀长度，用于失配时跳转；2. 构建过程用双指针i和j，比较pattern[i]与pattern[j]，相等则更新next[i]=j+1，不等则回退j=next[j-1]；3. 匹配阶段遍历主串，字符相等时双指针进，不等且j>0时j回退，j=0则主串指针进；4. 当j等于模式串长时记录匹配位置并继续搜索。时间复杂度O(m+n)。完整实现包含buildNext与kmpSearch函数，示例中查找”ABABC”在”ABABDABACDABABCABC”中的位置，输出匹配起始下标。核心是利用模式串自身结构减少冗余比较。
在C++中实现KMP（Knuth-Morris-Pratt）字符串匹配算法，核心是通过预处理模式串生成一个部分匹配表（通常称为next数组），避免在匹配失败时回溯主串的指针，从而将时间复杂度优化到O(m + n)。
1. 理解next数组的构建
next数组记录的是模式串每个位置之前的最长相等前后缀长度。这个信息用于在匹配失败时决定模式串应该跳到哪个位置继续比较。
构建next数组的过程如下：
初始化next[0] = 0（或-1，取决于实现方式）使用两个指针：i遍历模式串，j表示当前最长前缀的长度如果模式串[i] == 模式串[j]，则next[i+1] = j+1，然后i和j都加1如果不等且j > 0，则回退j = next[j-1]如果j为0，则next[i+1] = 0，i加1
2. 构建next数组代码实现
vector buildNext(const string& pattern) { int n = pattern.size(); 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;}
3. KMP主匹配过程
使用构建好的next数组，在主串中查找模式串出现的位置。
立即学习“C++免费学习笔记（深入）”；
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 m = text.size(), n = 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 == n) { matches.push_back(i - n + 1); j = next[j - 1]; // 继续找下一个匹配 }}return matches;
}
4. 完整示例调用
#include #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;
}
基本上就这些。KMP的关键在于理解next数组的含义——它保存了模式串自身的结构信息，使得我们可以在失配时跳过不必要的比较。只要把构建next和主匹配两个步骤写清楚，整个算法就很清晰了。
以上就是c++++怎么实现KMP字符串匹配算法_c++ KMP字符串匹配实现方法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1478073.html
微信扫一扫 
支付宝扫一扫 
