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 <iostream>
#include <vector>
#include <string>
<p>std::vector<int> buildNext(const std::string& pattern) {
int n = pattern.length();
std::vector<int> next(n, 0);
int j = 0;
for (int i = 1; i < n; ++i) {
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j - 1];
}
if (pattern[i] == pattern[j]) {
++j;
}
next[i] = j;
}
return next;
}</p><p>std::vector<int> kmpSearch(const std::string& text, const std::string& pattern) {
std::vector<int> matches;
if (pattern.empty()) return matches;</p><pre class='brush:php;toolbar:false;'>auto next = buildNext(pattern);
int m = text.length();
int n = pattern.length();
int j = 0;
for (int i = 0; i < m; ++i) {
while (j > 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;
}
法语写作助手
31
法语助手旗下的AI智能写作平台，支持语法、拼写自动纠错，一键改写、润色你的法语作文。
31
查看详情
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++ ai ios stream String auto 字符串 int 指针 算法
大家都在看：
c++怎么使用范围for循环(range-based for)_c++范围for循环语法讲解
c++中mutex(互斥锁)怎么使用_c++多线程互斥锁用法详解
c++中如何使用lambda表达式_c++ lambda表达式语法与应用示例
c++怎么实现一个简单的线程池_c++ 简单线程池实现方法
c++中怎么连接两个string_c++字符串拼接方法
c++中mutex(互斥锁)怎么使用_c++多线程互斥锁用法详解
c++中如何使用lambda表达式_c++ lambda表达式语法与应用示例
c++怎么实现一个简单的线程池_c++ 简单线程池实现方法
c++中怎么连接两个string_c++字符串拼接方法
本站资料仅供学习交流使用请勿商业运营，严禁从事违法，侵权等任何非法活动，否则后果自负！
THE END
暂无评论内容