您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 3461 Oulipo - KMP 算法大規模字符串模式匹配計數

編輯：關於C++

問題描述

給定模式串 W（長度 ≤ 10,000）和文本串 T（長度 ≤ 1,000,000），統計 W 在 T 中出現的次數（允許重疊）。僅包含大寫字母 A-Z。多測試用例。

範例：

W = BAPC, T = BAPC          → 1
W = AZA,  T = AZAZAZA       → 3 (重疊匹配)
W = VERDI, T = AVERDXIVYERDIAN → 0

KMP 算法核心：Next 陣列

next[i] 表示模式串前 i 個字符的最長真前綴同時也是後綴的長度。匹配失敗時，模式串可根據 next 陣列跳過無需比較的位置。

Next 陣列構建（標準版）

void getNext(const char* p, int len, int* next) {
    int i = 0, j = -1;
    next[0] = -1;
    while (i < len) {
        if (j == -1 || p[i] == p[j]) 
            next[++i] = ++j;
        else 
            j = next[j];
    }
}

KMP 匹配過程

int kmp(const char* s, int ls, const char* p, int lp, int* next) {
    int i = 0, j = 0, count = 0;
    while (i < ls) {
        if (j == -1 || s[i] == p[j]) {
            ++i; ++j;
        } else {
            j = next[j];
        }
        if (j == lp) {        // 找到一次匹配
            ++count;
            j = next[j];      // 允許重疊：繼續從 next[j] 位置匹配
        }
    }
    return count;
}

完整代碼（優化輸入輸出）

#include 
#include 
#include 
using namespace std;

const int MAXN = 1000010;
char T[MAXN], W[MAXN];
int nxt[MAXN];

void getNext(const char* p, int len) {
    int i = 0, j = -1;
    nxt[0] = -1;
    while (i < len) {
        if (j == -1 || p[i] == p[j]) nxt[++i] = ++j;
        else j = nxt[j];
    }
}

int kmp(const char* s, int ls, const char* p, int lp) {
    int i = 0, j = 0, cnt = 0;
    while (i < ls) {
        if (j == -1 || s[i] == p[j]) { ++i; ++j; }
        else j = nxt[j];
        if (j == lp) { ++cnt; j = nxt[j]; }
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tcases; scanf("%d", &tcases);
    while (tcases--) {
        scanf("%s%s", W, T);
        int lp = strlen(W), ls = strlen(T);
        getNext(W, lp);
        printf("%d\n", kmp(T, ls, W, lp));
    }
    return 0;
}