AC自動機詳解：多模式匹配的高效利器（原理、構建與代碼模板）

Aho-Corasick 自動機（AC自動機）是1975年貝爾實驗室提出的多模式匹配算法，核心思想是將多個模式串構建為 Trie 字典樹，並引入 失敗指針 實現失配時的快速跳轉，實現 O(N + M + Z) 的匹配複雜度（N 為文本長度，M 為模式總長，Z 為匹配數）。

核心數據結構

const int MAXN = 10000000;
struct Node {
    int count;          // 是否為單詞結尾
    Node* next[26];     // 26個子節點
    Node* fail;         // 失敗指針
};
Node* q[MAXN];          // BFS構建失敗指針用隊列
char keyword[55];       // 模式串
char str[1000010];      // 主串（待匹配文本）
int head, tail;         // 隊列頭尾指針

三步構建流程

1. 構建 Trie 字典樹

逐字符插入模式串，節點不存在則創建，最後節點 count++ 標記單詞結尾。

void insert(char* word, Node* root) {
    Node* p = root;
    for (int i = 0; word[i]; i++) {
        int idx = word[i] - 'a';
        if (!p->next[idx]) {
            Node* newNode = (Node*)malloc(sizeof(Node));
            memset(newNode->next, 0, sizeof(newNode->next));
            newNode->count = 0; newNode->fail = NULL;
            p->next[idx] = newNode;
        }
        p = p->next[idx];
    }
    p->count++;
}

2. 構建失敗指針（BFS層序遍歷）

規則：根的子節點 fail 指向根；其他節點沿父節點 fail 回溯，找到同字符子節點則指向它，否則指向根。

void build_ac_automation(Node* root) {
    head = 0; tail = 1; q[head] = root;
    while (head < tail) {
        Node* temp = q[head++];
        for (int i = 0; i < 26; i++) {
            if (temp->next[i]) {
                if (temp == root) temp->next[i]->fail = root;
                else {
                    Node* p = temp->fail;
                    while (p) {
                        if (p->next[i]) { temp->next[i]->fail = p->next[i]; break; }
                        p = p->fail;
                    }
                    if (!p) temp->next[i]->fail = root;
                }
                q[tail++] = temp->next[i];
            }
        }
    }
}

3. 模式匹配查詢

沿 Trie 匹配，失配時跳轉 fail 指針；匹配到單詞結尾（count > 0）則統計並標記 count = -1 防重複計數，繼續沿 fail 回溯查找其他可能匹配的單詞。

int query(Node* root) {
    int cnt = 0, len = strlen(str);
    Node* p = root;
    for (int i = 0; i < len; i++) {
        int idx = str[i] - 'a';
        while (!p->next[idx] && p != root) p = p->fail;
        p = p->next[idx] ? p->next[idx] : root;
        Node* temp = p;
        while (temp != root) {
            if (temp->count > 0) { cnt += temp->count; temp->count = -1; }
            else break;
            temp = temp->fail;
        }
    }
    return cnt;
}

完整可編譯模板（含主函數）

#include 
#include 
#include 
#define KIND 26
const int MAXN = 10000000;

struct Node { int count; Node* next[KIND]; Node* fail; };
Node *q[MAXN], *root;
char keyword[55], str[1000010];
int head, tail;

// insert, build_ac_automation, query 同上

int main() {
    int T, n, ans;
    scanf("%d", &T);
    while (T--) {
        root = (Node*)malloc(sizeof(Node));
        memset(root->next, 0, sizeof(root->next));
        root->fail = NULL; root->count = 0;
        scanf("%d", &n); getchar();
        for (int i = 0; i < n; i++) {
            scanf("%s", keyword); getchar();
            insert(keyword, root);
        }
        scanf("%s", str);
        build_ac_automation(root);
        ans = query(root);
        printf("%d\n", ans);
        // 此處應釋放內存，略
    }
    return 0;
}

關鍵點總結

• Trie 樹存儲所有模式串，共享公共前綴，空間高效。
• 失敗指針實質是「最長公共後綴」鏈接，使失配後無需回退主串指針。
• 輸出鏈：匹配時沿 fail 指針回溯，可發現所有以當前位置結尾的模式串。
• 應用場景：敏感詞過濾、病毒特徵庫匹配、多關鍵詞檢索等。