HDU 1686 Oulipo：KMP 算法統計模式串出現次數

HDU 1686 Oulipo：KMP 算法統計出現次數

給定單詞 W（長 ≤ 10,000）和文本 T（長 ≤ 1,000,000），統計 W 在 T 中出現的次數（可重疊）。多測試用例，字符集大寫字母。

KMP 核心

預處理 next 數組（失敗函數）：next[i] 表示模式串前 i 個字符的最長真前綴同時也是後綴的長度。匹配時，失配則模式串指針回退至 next[j]，文本指針不回退。時間複雜度 O(|W| + |T|)。

代碼實現

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <queue>
using namespace std;
char s2[10010], s1[1000010];
int sum, next[10010];
void get_next(int len) {
    int i = 0, j = -1; next[0] = -1;
    while (i < len) {
        if (j == -1 || s2[i] == s2[j]) { ++i; ++j; next[i] = j; }
        else j = next[j];
    }
}
void kmp(int len1, int len2) {
    int i = 0, j = 0; get_next(len2);
    while (i < len1) {
        if (j == -1 || s1[i] == s2[j]) { ++i; ++j; }
        else j = next[j];
        if (j == len2) { sum++; j = next[j]; }
    }
}
int main() {
    int t; scanf("%d", &t);
    while (t--) {
        getchar(); scanf("%s", s2); scanf("%s", s1);
        int len1 = strlen(s1), len2 = strlen(s2); sum = 0;
        kmp(len1, len2); printf("%d\n", sum);
    }
    return 0;
}

標準 KMP 模板，注意 next 數組構建邏輯與匹配時的指針移動。大數據量下需關閉同步 I/O 或用 scanf/printf。