題幹與適用場景
這是日誌過濾、敏感詞檢測或編輯器高亮中常見的多模式匹配題。設關鍵字總長度為 M、文字長度為 N，要求回報每個匹配的起點與關鍵字編號。關鍵字在建立階段固定，文字可能很長，面試官希望你說明預處理、掃描複雜度與重複匹配如何處理。
面試官考察點
面試官考察你能否把 Trie 的前綴共用擴展為有限狀態機。強回答會建立失敗連結、沿失敗鏈繼承輸出，並解釋每個字元只觸發有限次狀態轉移；普通回答只說「用 Trie 搜尋」，卻無法處理後綴重疊或失配回退。
回答前需要澄清的問題
- 是否區分大小寫、Unicode 正規化或位元組？字元定義會改變 Trie 與位置單位。
- 是否需要回傳重疊匹配與同一結束位置的多個關鍵字？這決定輸出鏈是否完整。
- 關鍵字是否會頻繁更新？靜態字典適合建立自動機，動態字典可能需要分塊重建。
- 位置按字元、位元組還是 UTF-16 code unit 計數？必須與呼叫方契約一致。
- 文字是否分塊到達？跨區塊掃描要保留目前狀態，不能每塊重設。
30 秒回答框架
「我先把關鍵字插入 Trie，再用 BFS 為每個節點建立失敗連結：它表示目前前綴失配後最長的可用後綴。每個節點合併自身和失敗節點的輸出列表。掃描文字時沿轉移或失敗連結移動，並回報目前節點輸出。建立複雜度與關鍵字總長度和邊數線性相關，掃描為 O(N + 匹配數)，串流分塊只需保留狀態。」
分步驟深入解答
- 建立 Trie。 每個節點保存子邊、失敗連結與輸出的關鍵字編號；關鍵字結束節點追加編號，不能只保存一個。
- 初始化失敗連結。 根節點的直接子節點失敗連結指向根；用佇列按深度處理其餘節點。
- 計算失敗轉移。 對節點的字元邊，沿父節點失敗連結尋找同字元邊；找不到就回到根。這樣掃描時無需重新比較文字字元。
- 聚合輸出。 將失敗目標的輸出追加到目前節點，或保存輸出連結以節省複製；後者要在查詢時沿鏈遍歷。
- 掃描文字。 每個字元先嘗試子邊，失配就沿失敗連結，直到找到邊或回到根；進入節點後回報全部輸出，位置由目前索引減關鍵字長度加一得到。
- 處理邊界。 重疊關鍵字自然會同時輸出；分塊輸入保留狀態。若輸出量巨大，應支援回呼、上限或分頁，避免把 O(匹配數) 結果一次放入記憶體。
簡單實作可把字元到子節點的映射設為雜湊表；固定小字元集可用陣列換取更快轉移。若關鍵字動態變化，按字典版本建立新自動機並原子切換，避免掃描過程看到半成品。
高品質示範回答
「我會先插入所有關鍵字並記錄每個終點的編號，然後 BFS 計算失敗連結。根的孩子失敗到根；其他邊沿父節點失敗鏈尋找同字元轉移，找不到就回根。節點輸出包含自身終點和失敗節點輸出，因此 he 與 she 在掃描 she 時都會回報。掃描每個字元只沿子邊或失敗連結移動，複雜度是 O(N + Z)，Z 是匹配數；預處理是 O(M) 加上邊表示開銷。文字分塊時保留狀態，字典更新則建立新版本後切換。」
常見錯誤
- 錯誤表現： 失配後把指標和文字一起回退 → 失敗原因： 退化為每個關鍵字重複掃描 → 修正方法： 使用失敗連結保持文字索引單調前進。
- 錯誤表現： 每個節點只保留一個輸出 → 失敗原因： 後綴關鍵字和重複終點會遺失 → 修正方法： 合併失敗鏈輸出或維護輸出連結。
- 錯誤表現： 認為掃描一定是 O(N) → 失敗原因： 輸出匹配本身可能達到 O(Z) → 修正方法： 明確回報 O(N + Z) 並設計串流輸出。
- 錯誤表現： 分塊處理時重設根狀態 → 失敗原因： 跨區塊關鍵字無法匹配 → 修正方法： 在區塊之間傳遞自動機狀態。
追問及應對
為什麼不對每個關鍵字使用 KMP？
分別執行 KMP 需要 O(KN) 掃描；Aho–Corasick 在共用 Trie 前綴後一次處理文字，更適合關鍵字集合固定且文字很長的場景。
失敗連結如何保證不漏匹配？
它指向目前字串的最長可用後綴；沿失敗鏈繼續走會列舉所有也是關鍵字前綴的後綴，因此輸出聚合能發現嵌套與重疊匹配。
記憶體被子節點雜湊表耗盡怎麼辦？
依字元集選擇陣列、緊湊邊表或雙陣列 Trie，並考慮輸出連結避免複製列表；先測量節點與邊數再決定壓縮策略。
關鍵字經常變化還能用嗎？
將字典版本化，在背景建立新自動機，完成驗證後原子替換讀取指標；短窗口內保留舊版本處理進行中的串流。