C++ AC 自動機（Aho-Corasick）完整實現：多模式匹配神器

AC 自動機是多模式字符串匹配的經典算法，構建 Trie + 失敗指標，可在 O(n + m + z) 時間內同時匹配多個模式（n=文本長度，m=模式總長，z=匹配數）。本文呈現一個生產級 C++17 實現，支援 Unicode、重疊匹配控制、全詞匹配、大小寫不敏感、區間樹去重等進階特性，代碼結構模塊化，可直接集成項目。

核心組件架構

關鍵特性

• 泛型字符型別：trie (char)、wtrie (wchar_t) 開箱即用
• 配置選項：
  • case_insensitive()：大小寫不敏感
  • remove_overlaps()：區間樹去重，保留最長匹配
  • only_whole_words()：邊界字符檢查，全詞匹配
• 輸出模式：
  • parse_text()：返回 emit 列表（位置+關鍵詞）
  • tokenise()：返回 token 序列（匹配/非匹配片段交替），適合高亮/替換

核心算法流程

1. 構建 Trie：insert(keyword) 逐字符建節點，終點記錄 emit
2. 構建失敗指標：BFS 層序遍歷，failure 指向最長真後綴對應節點，合併 emit 集合
3. 查詢：狀態機遍歷文本，next_state(c) 跳轉，失敗時沿 failure 回退至根
4. 後處理：全詞檢查、區間樹去重、輸出封裝

使用示例

#include "aho_corasick.hpp"
using namespace aho_corasick;

int main() {
    trie ac;
    ac.insert("he"); ac.insert("she"); ac.insert("his"); ac.insert("hers");
    ac.remove_overlaps().case_insensitive(); // 配置

    string text = "ushers";
    auto emits = ac.parse_text(text);
    for (auto& e : emits)
        cout << "[" << e.get_start() << "," << e.get_end() << "] " << e.get_keyword() << endl;

    // 輸出:
    // [1,2] he
    // [0,2] she
    // [2,5] hers
    // [3,5] he (若未去重)
    return 0;
}

代碼亮點

• RAII 內存管理：unique_ptr 管理 Trie 節點，無洩漏
• 區間樹去重：interval_tree::remove_overlaps() 以 O(k log k) 去除重疊，保留最長匹配
• 邊界檢查：isalpha 判斷詞邊界，支援全詞匹配
• 標準庫只依賴：無第三方依賴，頭文件即用

效能複雜度

適用場景

• 關鍵詞過濾/審核（敏感詞、廣告詞）
• 日誌/威脅情報多特徵掃描
• 基因序列多模式比對
• IDE/編輯器多關鍵字高亮
• NLP 分詞/實體識別預處理

源碼獲取

完整頭文件 aho_corasick.hpp 含所有模板實現（約 500 行），採用 MIT 許可證，可直接複製到項目 include/ 目錄使用。