c++ kmp算法代码 c++字符串匹配算法详解_技术教程

KMP算法通过构建next数组实现高效字符串匹配，避免主串指针回溯，时间复杂度O(n+m)；next数组记录模式串各位置最长相等真前后缀长度，用于失配时确定模式串的滑动位置；例如模式串"ABABC"的next数组为[0,0,1,2,0]；匹配过程中，当字符不匹配且j>0时，j回退到next[j-1]，否则i++；最终输出所有匹配起始位置，如主串"ABABDABACDABABCABC"中找到"ABABC"在位置8匹配。

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在一个主串（文本串）中查找一个子串（模式串）的出现位置。与暴力匹配相比，KMP避免了主串指针的回溯，时间复杂度为 O(n + m)，其中 n 是主串长度，m 是模式串长度。

核心思想：利用部分匹配表（Next数组）

KMP 的关键在于预处理模式串，构建一个 next 数组（也叫失败函数或部分匹配表），记录模式串每个位置之前的最长相等真前后缀长度。当匹配失败时，利用 next 数组决定模式串应该跳到哪个位置继续匹配，而不是从头开始。

举个例子：

模式串 "ABABC" 的 next 数组为 [0, 0, 1, 2, 0]。解释如下：

next[0] = 0（单个字符无前后缀）
next[1] = 0（"AB" 无公共前后缀）
next[2] = 1（"ABA" 中前缀 "A" 和后缀 "A" 相同）
next[3] = 2（"ABAB" 中前缀 "AB" 和后缀 "AB" 相同）
next[4] = 0（"ABABC" 无公共前后缀）

构建 Next 数组（预处理）

使用双指针法构造 next 数组，类似于在模式串自己和自己做匹配：

void getNext(const string& pattern, vector& next) {
    int m = pattern.length();
    next.resize(m);
    next[0] = 0;
    int len = 0; // 当前最长相等前后缀长度
    int i = 1;

    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            next[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = next[len - 1]; // 回退 len
            } else {
                next[i] = 0;
                i++;
            }
        }
    }
}

KMP 匹配过程

主串和模式串进行匹配，当字符不相等时，利用 next 数组移动模式串指针：

#include 
#include 
#include 
using namespace std;

// KMP 主函数，返回所有匹配位置
vector kmpSearch(const string& text, const string& pattern) {
    vector result;
    int n = text.length();
    int m = pattern.length();

    if (m == 0) return result;

    vector next;
    getNext(pattern, next);

    int i = 0; // text 指针
    int j = 0; // pattern 指针

    while (i < n) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        }

        if (j == m) {
            result.push_back(i - j); // 找到一次匹配
            j = next[j - 1];
        } else if (i < n && text[i] != pattern[j]) {
            if (j != 0) {
                j = next[j - 1];
            } else {
                i++;
            }
        }
    }

    return result;
}

完整可运行示例

```cpp int main() { string text = "ABABDABACDABABCABC"; string pattern = "ABABC";

vector matches = kmpSearch(text, pattern);

if (matches.empty()) {
    cout << "未找到匹配" << endl;
} else {
    cout << "模式串在以下位置匹配: ";
    for (int pos : matches) {
        cout << pos << " ";
    }
    cout << endl;
}

return 0;

}

输出结果：

模式串在以下位置匹配: 8