c++怎么实现KMP字符串匹配算法_c++ KMP字符串匹配实现方法

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<int> buildNext(const string& pattern) {
    int n = pattern.size();
    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;
}

3. KMP主匹配过程

使用构建好的next数组，在主串中查找模式串出现的位置。

立即学习“C++免费学习笔记（深入）”；

• i用于遍历主串，j用于遍历模式串
• 如果字符匹配，i和j都前进
• 如果不匹配且j > 0，则j回退到next[j-1]
• 如果j为0，则只让i前进
• 当j等于模式串长度时，说明找到一次匹配，记录起始位置并继续搜索

腾讯智影-AI数字人

基于AI数字人能力，实现7*24小时AI数字人直播带货，低成本实现直播业务快速增增，全天智能在线直播

73

查看详情

vector<int> kmpSearch(const string& text, const string& pattern) {
    vector<int> matches;
    if (pattern.empty()) return matches;
<pre class='brush:php;toolbar:false;'>vector<int> next = buildNext(pattern);
int m = text.size(), n = pattern.size();
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;

}

4. 完整示例调用

#include <iostream>
#include <vector>
#include <string>
using namespace std;
<p>int main() {
string text = "ABABDABACDABABCABC";
string pattern = "ABABC";</p><pre class='brush:php;toolbar:false;'>vector<int> 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字符串匹配实现方法的详细内容，更多请关注php中文网其它相关文章！