HDU 1686 Oulipo：KMP 算法求模式串在主串中出現次數（可重疊）

問題描述

給定模式串 P（長 ≤ 10000）和主串 S（長 ≤ 1000000），求 P 在 S 中出現的次數，**可重疊**。多測試用例。

樣例：

Input:
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

Output:
1
3
0

第二例 AZA 在 AZAZAZA 中出現 3 次：位置 0, 2, 4（重疊）。

KMP 核心：next 數組（失敗函數）

next[j] = 模式串 P[0..j-1] 的**最長真前綴同時也是後綴**的長度。
失配時，模式串右移 j - next[j] 位，避免主串回溯。

關鍵優化：next[len] 用於匹配成功後的跳轉

匹配成功（j == len）時，利用 next[len] 直接跳轉繼續匹配，**支持重疊**。
這是本題 AC 關鍵：普通 KMP 匹配成功後常置 j=0，會漏掉重疊匹配。

完整 C++ 代碼（AC 版）

#include <bits/stdc++.h>
using namespace std;

const int MAX_S = 1000005;
const int MAX_P = 10005;

char S[MAX_S], P[MAX_P];
int nxt[MAX_P];
int lenS, lenP;

void build_next() {
    nxt[0] = -1;
    for (int i = 1, j = -1; i <= lenP; ++i) {
        while (j >= 0 && P[j] != P[i-1]) j = nxt[j];
        ++j;
        if (i == lenP || P[i] != P[j]) nxt[i] = j;
        else nxt[i] = nxt[j]; // 優化：跳過相同字符
    }
}

int kmp_search() {
    int cnt = 0;
    for (int i = 0, j = 0; i < lenS; ++i) {
        while (j >= 0 && (j == lenP || P[j] != S[i])) j = nxt[j];
        ++j;
        if (j == lenP) {
            ++cnt;
            j = nxt[j]; // 關鍵：用 next[lenP] 繼續匹配，支持重疊
        }
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while (T--) {
        cin >> P >> S;
        lenP = strlen(P);
        lenS = strlen(S);
        build_next();
        cout << kmp_search() << '\n';
    }
    return 0;
}

next 數組構建詳解

以 P = "ABABCABAA" 為例：

i:      0 1 2 3 4 5 6 7 8
P[i]:   A B A B C A B A A
nxt[i]: -1 0 0 1 2 0 1 2 3
nxt[9]: 3  (lenP=9)

nxt[9]=3 表示整個模式串的最長前後綴長度為 3（"ABA"）。匹配成功後跳轉到 j=3，即保留 "ABA" 作為下一次匹配的已匹配前綴。

可視化理解：匹配成功後的跳轉

主串:     A B A B A B C A B A B A A B
模式串:   A B A B C A B A
                    ↑匹配成功
下一步:           A B A B C A B A
                    ↑跳轉到這裡 (j = nxt[8] = 3)

因為前綴 ABA = 後綴 ABA，直接對齊繼續比較後續字符，無需主串回退。

複雜度分析

• 預處理：O(m) — build_next 單次遍歷
• 匹配：O(n) — 主串指針 i 只增不減
• 總體：O(n + m)，空間 O(m)

常見坑點

1. next 數組大小需 lenP + 1，存儲 next[lenP]
2. 匹配成功後 **必須用 j = nxt[j]**，不能 j = 0，否則漏重疊
3. 輸入可能含空行/空格，用 cin >> P >> S 自動跳過空白
4. 多測試用例需在循環內重置所有變量

總結

HDU 1686 是 KMP 算法重疊匹配場景的標準練習。關鍵在於理解 next[len] 的物理意義：模式串整體的最長前後綴長度。掌握「匹配成功後跳轉 next[len]」這一技巧，即可輕鬆解決所有可重疊模式匹配問題。