C++ 實現 KMP 模式匹配算法詳解

KMP 核心思想

在文本 T 中查找模式 P，利用「部分匹配表」（next 數組）避免回溯文本指針，實現 O(|T|+|P|) 時間。

next 數組定義

next[i] = 模式串前綴 P[0…i] 的最長真前綴同時也是後綴的長度。
約定 next[0] = -1 便於統一邏輯。

構建 next 數組

void buildNext(const string &pat, vector<int> &next) {
    int m = pat.size(); next.assign(m, 0);
    next[0] = -1;
    for (int i = 1, j = -1; i < m; ++i) {
        while (j >= 0 && pat[j + 1] != pat[i]) j = next[j];
        if (pat[j + 1] == pat[i]) ++j;
        next[i] = j;
    }
}

匹配過程

vector<int> kmpSearch(const string &text, const string &pat) {
    vector<int> next, pos;
    buildNext(pat, next);
    for (int i = 0, j = -1; i < (int)text.size(); ++i) {
        while (j >= 0 && pat[j + 1] != text[i]) j = next[j];
        if (pat[j + 1] == text[i]) ++j;
        if (j == (int)pat.size() - 1) {
            pos.push_back(i - j); // 匹配起始位置
            j = next[j];          // 繼續找下一個
        }
    }
    return pos;
}

完整可運行示例

#include <iostream>
#include <string>
#include <vector>
using namespace std;

void buildNext(const string &pat, vector<int> &next) {
    int m = pat.size(); next.resize(m);
    next[0] = -1;
    for (int i = 1, j = -1; i < m; ++i) {
        while (j >= 0 && pat[j + 1] != pat[i]) j = next[j];
        if (pat[j + 1] == pat[i]) ++j;
        next[i] = j;
    }
}
vector<int> kmpSearch(const string &text, const string &pat) {
    vector<int> next, ans;
    buildNext(pat, next);
    for (int i = 0, j = -1; i < (int)text.size(); ++i) {
        while (j >= 0 && pat[j + 1] != text[i]) j = next[j];
        if (pat[j + 1] == text[i]) ++j;
        if (j == (int)pat.size() - 1) {
            ans.push_back(i - j);
            j = next[j];
        }
    }
    return ans;
}
int main() {
    string text, pat;
    while (cin >> text >> pat) {
        auto pos = kmpSearch(text, pat);
        cout << "Matches at: ";
        for (int p : pos) cout << p << ' ';
        cout << '\n';
    }
}

關鍵點總結

• next 數組構建與匹配均為線性時間。
• 模式串為空需特判。
• 支援重疊匹配（如 AAA 在 AAAA 中出現兩次）。