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

KMP算法通过构建next数组避免回溯，实现O(n+m)字符串匹配。首先用双指针法构造模式串的最长相等前后缀数组，再利用该数组在主串中滑动匹配，失配时根据next跳转，最终找出所有匹配位置。

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配方法，能在O(n + m)时间内完成模式串在主串中的查找，避免了暴力匹配中不必要的回溯。下面介绍C++中如何实现KMP算法。

1. 理解KMP的核心思想

KMP的关键在于预处理模式串，构建一个next数组（也叫失配函数或部分匹配表），记录每个位置前缀和后缀的最长公共长度。当匹配失败时，利用next数组决定模式串应该向右滑动多少位，而不是从头开始比较。

例如，模式串 "ABABC" 的 next 数组为 [0, 0, 1, 2, 0]。

2. 构建next数组

next[i] 表示模式串前 i+1 个字符中，最长相等前后缀的长度（不包含整个子串本身）。构造过程类似双指针：

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

代码如下：

Batch GPT

使用AI批量处理数据、自动执行任务

下载

vector buildNext(const string& pattern) {
    int m = pattern.size();
    vector next(m, 0);
    int j = 0;
    for (int i = 1; i < m; ++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数组，在主串中滑动匹配：

完整搜索函数：

vector kmpSearch(const string& text, const string& pattern) {
    vector matches;
    if (pattern.empty()) return matches;
vector next = buildNext(pattern);
int n = text.size(), m = pattern.size();
int j = 0;

for (int i = 0; i < n; ++i) {
    while (j > 0 && text[i] != pattern[j]) {
        j = next[j - 1];
    }
    if (text[i] == pattern[j]) {
        j++;
    }
    if (j == m) {
        matches.push_back(i - m + 1);
        j = next[j - 1]; // 准备下一次匹配
    }
}
return matches;
}

4. 使用示例
测试代码：
#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;
}

输出：Pattern found at positions: 8
基本上就这些。KMP算法难点在next数组的理解与构造，一旦掌握，就能高效处理大规模文本匹配问题。