ACM 敏感詞過濾：KMP / Boyer-Moore / AC 自動機演算法選型與 C++ 實現要點

題目重述

給定敏感詞 w、文本 p (長度 ≤ 5×10⁶)，**反覆**在 p 中尋找 w 第一次出現並刪除，直到不再出現。輸出最終文本。

範例：w=abc, p=aaabcbc → 刪除 abc 得 aabc → 再刪 abc 得 a。

演算法選型指南

本題關鍵：刪除後需**重新掃描**前文

刪除 w 可能導致前後字符拼接形成新的 w (如 aabc 刪中間 abc 後剩 a，但 aaabcbc 刪第一個 abc 後 a+bc 不形成新詞)。**單次 KMP/BM 不夠**，需模擬棧或雙指針原地處理。

推薦：棧模擬 + KMP 邊界檢查 (O(N) 時間, O(N) 空間)

string censor(string w, string p) {
    int n = p.size(), m = w.size();
    if (m == 0) return p;
    
    // KMP next 陣列 (0-based)
    vector nxt(m);
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && w[i] != w[j]) j = nxt[j-1];
        if (w[i] == w[j]) j++;
        nxt[i] = j;
    }
    
    string res; res.reserve(n);
    vector matchLen; matchLen.reserve(n);  // 對應 res 每位的匹配長度
    
    for (char c : p) {
        res.push_back(c);
        int j = matchLen.empty() ? 0 : matchLen.back();
        while (j > 0 && c != w[j]) j = nxt[j-1];
        if (c == w[j]) j++;
        matchLen.push_back(j);
        
        if (j == m) {  // 找到敏感詞
            res.resize(res.size() - m);
            matchLen.resize(matchLen.size() - m);
        }
    }
    return res;
}

關鍵點解析

1. res 當棧：push_back 進字符，匹配成功 resize 彈出
2. matchLen 同步棧：記錄每位對應的 KMP 狀態，回退時 O(1) 恢復
3. 單次掃描：無需刪除後重頭掃描，總時間 O(N)
4. 記憶體優化：matchLen 可用 vector (m ≤ 5e6 < 65535? 否則用 int)

若 w 為多個敏感詞 (多模式)

必須用 **AC 自動機 (Aho-Corasick)** + 棧模擬。構建 Trie + 失敗指針，掃描時同步維護狀態棧，刪除時回退到失敗指針對應狀態。

測試案例

總結

ACM 敏感詞刪除題核心是**單次線性掃描 + 棧模擬刪除 + KMP 狀態同步**。暴力 find/erase 會 TLE。KMP/BM 單模式足夠，多模式上 AC 自動機。代碼關鍵：res 與 matchLen 雙棧同步，刪除時同步回退。