HDU 1618 Oulipo：KMP 算法模板與常見坑

問題描述

給定模式串 word（長 ≤ 10,000）和文本串 txt（長 ≤ 1,000,000），求模式串在文本串中出現的次數（可重疊）。多測試用例。

KMP 核心：next 數組

next[i] = 模式串前綴 [0..i] 的最長真前綴同時是後綴的長度。構建 O(m)：

j = 0
for i = 1..m-1:
    while j > 0 && word[i] != word[j] j = next[j-1]
    if word[i] == word[j] j++
    next[i] = j

匹配過程

i = 0, j = 0
while i < n:
    while j > 0 && txt[i] != word[j] j = next[j-1]
    if txt[i] == word[j] j++
    if j == m: ans++; j = next[j-1] // 關鍵：找到匹配後 j 回退，允許重疊
    i++

常見坑：i++ 位置

匹配成功分支 if (j == m) 中 不能 再 i++，否則會漏掉重疊匹配並導致邏輯錯誤/超時。正確流程：所有分支最後統一 i++。

參考代碼（C++）

#include <cstdio>
#include <cstring>
const int MAX_TXT = 1000001;
const int MAX_WORD = 10001;

char word[MAX_WORD], txt[MAX_TXT];
int nxt[MAX_WORD];
int m, n;

void build_next() {
    nxt[0] = 0;
    for (int i = 1, j = 0; i < m; ) {
        if (word[i] == word[j]) nxt[i++] = ++j;
        else if (j > 0) j = nxt[j-1];
        else i++;
    }
}

int kmp_search() {
    int ans = 0;
    for (int i = 0, j = 0; m - j <= n - i; ) {
        if (word[j] == txt[i]) {
            j++; i++;
            if (j == m) {
                ans++;
                j = nxt[j-1];
            }
        } else if (j > 0) j = nxt[j-1];
        else i++;
    }
    return ans;
}

int main() {
    int T; scanf("%d", &T); getchar();
    while (T--) {
        fgets(word, MAX_WORD, stdin); word[strcspn(word, "\n")] = 0;
        fgets(txt, MAX_TXT, stdin); txt[strcspn(txt, "\n")] = 0;
        m = strlen(word); n = strlen(txt);
        build_next();
        printf("%d\n", kmp_search());
    }
    return 0;
}

複雜度

• 構建 next：O(m)
• 匹配：O(n)
• 總時間：O(m+n)，線性級，極快