C++如何实现KMP字符串匹配算法_C++高效字符串查找算法KMP原理与实现-C++-PHP中文网

C++如何实现KMP字符串匹配算法_C++高效字符串查找算法KMP原理与实现

裘德小鎮的故事

发布： 2025-11-21 16:31:02

原创

955人浏览过

KMP算法通过构建next数组实现高效字符串匹配，利用最长相等前后缀信息避免主串指针回溯，在O(n+m)时间内完成搜索。

c++如何实现kmp字符串匹配算法_c++高效字符串查找算法kmp原理与实现

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，能够在O(n + m)时间内完成模式串在主串中的查找，避免了暴力匹配中不必要的回溯。其核心思想是利用已匹配的部分信息，通过预处理模式串构造“部分匹配表”（即next数组），跳过不可能匹配的位置。

理解KMP的核心：next数组

在KMP算法中，关键在于构建模式串的next数组，它记录了模式串每个位置之前的最长相等前后缀长度。当发生失配时，可以借助next数组决定模式串应向右滑动多少位，而无需回退主串指针。

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

构建next数组的过程本质上是一个“模式串自我匹配”的过程，使用双指针技巧：

i 遍历模式串从 1 到 len-1
j 表示当前最长相等前后缀的长度，初始为 0
若 pattern[i] == pattern[j]，则 next[i++] = ++j
否则回退 j = next[j-1]（如果 j > 0），直到匹配或 j=0

构建next数组的代码实现

void buildNext(const string& pattern, vector<int>& next) {
    int n = pattern.length();
    next.resize(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;
    }
}

登录后复制

KMP主匹配过程

有了next数组后，主串与模式串的匹配就可以线性进行。主串指针不回退，只移动模式串指针。

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

GPTKit

一个AI文本生成检测工具

108

查看详情

i 遍历主串，j 遍历模式串
字符相等时，i++，j++
失配时，若 j > 0，则 j = next[j-1]；否则 i++
当 j 达到模式串长度时，说明找到一次匹配，记录位置并继续搜索

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

登录后复制

}

完整使用示例

#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;

登录后复制

}

输出结果为：
Pattern found at positions: 8
表示模式串首次出现在主串第8个位置（从0开始）。

基本上就这些。KMP的关键在于理解next数组的意义和构建逻辑，一旦掌握，匹配过程非常清晰高效。

以上就是C++如何实现KMP字符串匹配算法_C++高效字符串查找算法KMP原理与实现的详细内容，更多请关注php中文网其它相关文章！