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

問題描述

給定模式串 b 和文本串 a，求 b 在 a 中出現的次數（可重疊）。經典 KMP 匹配問題。

KMP 核心流程

1. 預處理 LCPS 數組：對模式串 b 計算 next 數組，記錄每個前綴的最長真前綴兼真後綴長度。
2. 主匹配循環：雙指針 i（文本）、j（模式）同步推進；失配時根據 next[j] 回退 j，i 不回退，保證 O(n+m) 複雜度。
3. 計數：每當 j == b_len，計數器加一，並令 j = next[j] 繼續尋找下一次匹配（允許重疊）。

關鍵代碼片段

void GetLCPS() {
    int j = 0, k = -1;
    int len = strlen(b);
    next[0] = -1;
    while (j < len) {
        if (k == -1 || b[k] == b[j]) next[++j] = ++k;
        else k = next[k];
    }
}

void KMP() {
    int i = 0, j = 0, ans = 0;
    int a_len = strlen(a), b_len = strlen(b);
    while (i < a_len) {
        if (j == -1 || a[i] == b[j]) { ++i; ++j; }
        else j = next[j];
        if (j == b_len) { ++ans; j = next[j]; }
    }
    printf("%d\n", ans);
}

複雜度分析

預處理 O(m)，匹配 O(n)，總時間 O(n+m)，空間 O(m)。適合長文本（10^6）與多測試用例場景。

注意事項

• 模式串長度可達 10^4，文本串 10^6，需用靜態大數組避免棧溢出。
• 輸入可能包含空行，建議用 scanf("%s") 讀取非空白字符串。