AC 自动机

概念讲解

什么是 AC 自动机？

AC 自动机是 KMP 算法和 Trie 的结合，用于多模式串匹配。

核心思想

  1. 构建 Trie 树
  2. 计算失配指针（类似 KMP 的 next 数组）
  3. 在 Trie 上进行匹配

实现

节点定义

123456789struct Node {
    int children[26];
    int fail;
    int count;
};

const int N = 100005;
Node trie[N];
int idx = 0;

构建 Trie

1234567891011void insert(string s) {
    int p = 0;
    for (char c : s) {
        int u = c - 'a';
        if (!trie[p].children[u]) {
            trie[p].children[u] = ++idx;
        }
        p = trie[p].children[u];
    }
    trie[p].count++;
}

构建失配指针

123456789101112131415161718192021222324void build() {
    queue<int> q;
    
    for (int i = 0; i < 26; i++) {
        if (trie[0].children[i]) {
            q.push(trie[0].children[i]);
        }
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int i = 0; i < 26; i++) {
            int v = trie[u].children[i];
            if (v) {
                trie[v].fail = trie[trie[u].fail].children[i];
                q.push(v);
            } else {
                trie[u].children[i] = trie[trie[u].fail].children[i];
            }
        }
    }
}

匹配

123456789101112131415161718int match(string s) {
    int p = 0;
    int result = 0;
    
    for (char c : s) {
        int u = c - 'a';
        p = trie[p].children[u];
        
        int temp = p;
        while (temp && trie[temp].count != -1) {
            result += trie[temp].count;
            trie[temp].count = -1;
            temp = trie[temp].fail;
        }
    }
    
    return result;
}

应用场景

1. 多模式串匹配

1int count = match(text);

2. 统计模式串出现次数

1// 在 match 函数中统计

考点分析

初赛考查方式

  1. 选择题： AC 自动机的概念
  2. 程序阅读： 理解 AC 自动机
  3. 编程题： AC 自动机应用

常见题型

  • 多模式串匹配
  • 统计模式串出现次数

例题精讲

例题 1：多模式串匹配

题目： 在文本串中查找多个模式串出现的次数。

解答：

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

struct Node {
    int children[26];
    int fail;
    int count;
};

const int N = 100005;
Node trie[N];
int idx = 0;

void insert(string s) {
    int p = 0;
    for (char c : s) {
        int u = c - 'a';
        if (!trie[p].children[u]) {
            trie[p].children[u] = ++idx;
        }
        p = trie[p].children[u];
    }
    trie[p].count++;
}

void build() {
    queue<int> q;
    
    for (int i = 0; i < 26; i++) {
        if (trie[0].children[i]) {
            q.push(trie[0].children[i]);
        }
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int i = 0; i < 26; i++) {
            int v = trie[u].children[i];
            if (v) {
                trie[v].fail = trie[trie[u].fail].children[i];
                q.push(v);
            } else {
                trie[u].children[i] = trie[trie[u].fail].children[i];
            }
        }
    }
}

int match(string s) {
    int p = 0;
    int result = 0;
    
    for (char c : s) {
        int u = c - 'a';
        p = trie[p].children[u];
        
        int temp = p;
        while (temp && trie[temp].count != -1) {
            result += trie[temp].count;
            trie[temp].count = -1;
            temp = trie[temp].fail;
        }
    }
    
    return result;
}

int main() {
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        insert(s);
    }
    
    build();
    
    string text;
    cin >> text;
    
    cout << match(text) << endl;
    
    return 0;
}

练习题

  1. 洛谷 P3808 AC 自动机（简单版）
查看答案

思路：AC 自动机模板题。

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

struct Node {
    int children[26];
    int fail;
    int count;
};

const int N = 1000005;
Node trie[N];
int idx = 0;

void insert(string s) {
    int p = 0;
    for (char c : s) {
        int u = c - 'a';
        if (!trie[p].children[u]) {
            trie[p].children[u] = ++idx;
        }
        p = trie[p].children[u];
    }
    trie[p].count++;
}

void build() {
    queue<int> q;
    
    for (int i = 0; i < 26; i++) {
        if (trie[0].children[i]) {
            q.push(trie[0].children[i]);
        }
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int i = 0; i < 26; i++) {
            int v = trie[u].children[i];
            if (v) {
                trie[v].fail = trie[trie[u].fail].children[i];
                q.push(v);
            } else {
                trie[u].children[i] = trie[trie[u].fail].children[i];
            }
        }
    }
}

int match(string s) {
    int p = 0;
    int result = 0;
    
    for (char c : s) {
        int u = c - 'a';
        p = trie[p].children[u];
        
        int temp = p;
        while (temp && trie[temp].count != -1) {
            result += trie[temp].count;
            trie[temp].count = -1;
            temp = trie[temp].fail;
        }
    }
    
    return result;
}

int main() {
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        insert(s);
    }
    
    build();
    
    string text;
    cin >> text;
    
    cout << match(text) << endl;
    return 0;
}
  1. 洛谷 P3796 AC 自动机（加强版）
查看答案

思路：AC 自动机，统计每个模式串出现的次数。

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

struct Node {
    int children[26];
    int fail;
    int count;
    int id;
};

const int N = 1000005;
Node trie[N];
int idx = 0;
int cnt[155];

void insert(string s, int id) {
    int p = 0;
    for (char c : s) {
        int u = c - 'a';
        if (!trie[p].children[u]) {
            trie[p].children[u] = ++idx;
        }
        p = trie[p].children[u];
    }
    trie[p].count++;
    trie[p].id = id;
}

void build() {
    queue<int> q;
    
    for (int i = 0; i < 26; i++) {
        if (trie[0].children[i]) {
            q.push(trie[0].children[i]);
        }
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int i = 0; i < 26; i++) {
            int v = trie[u].children[i];
            if (v) {
                trie[v].fail = trie[trie[u].fail].children[i];
                q.push(v);
            } else {
                trie[u].children[i] = trie[trie[u].fail].children[i];
            }
        }
    }
}

void match(string s) {
    int p = 0;
    
    for (char c : s) {
        int u = c - 'a';
        p = trie[p].children[u];
        
        int temp = p;
        while (temp) {
            if (trie[temp].id) {
                cnt[trie[temp].id] += trie[temp].count;
            }
            temp = trie[temp].fail;
        }
    }
}

int main() {
    int n;
    while (cin >> n && n) {
        memset(trie, 0, sizeof(trie));
        memset(cnt, 0, sizeof(cnt));
        idx = 0;
        
        string patterns[n + 1];
        for (int i = 1; i <= n; i++) {
            cin >> patterns[i];
            insert(patterns[i], i);
        }
        
        build();
        
        string text;
        cin >> text;
        match(text);
        
        int maxCnt = 0;
        for (int i = 1; i <= n; i++) {
            maxCnt = max(maxCnt, cnt[i]);
        }
        
        cout << maxCnt << endl;
        for (int i = 1; i <= n; i++) {
            if (cnt[i] == maxCnt) {
                cout << patterns[i] << endl;
            }
        }
    }
    
    return 0;
}
  1. 洛谷 P5357 AC 自动机（二次加强版）
查看答案

思路：AC 自动机 + 拓扑排序优化。

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

struct Node {
    int children[26];
    int fail;
    int count;
    int id;
};

const int N = 200005;
Node trie[N];
int idx = 0;
int cnt[N], inDegree[N];

void insert(string s, int id) {
    int p = 0;
    for (char c : s) {
        int u = c - 'a';
        if (!trie[p].children[u]) {
            trie[p].children[u] = ++idx;
        }
        p = trie[p].children[u];
    }
    trie[p].count++;
    trie[p].id = id;
}

void build() {
    queue<int> q;
    
    for (int i = 0; i < 26; i++) {
        if (trie[0].children[i]) {
            q.push(trie[0].children[i]);
        }
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int i = 0; i < 26; i++) {
            int v = trie[u].children[i];
            if (v) {
                trie[v].fail = trie[trie[u].fail].children[i];
                inDegree[trie[v].fail]++;
                q.push(v);
            } else {
                trie[u].children[i] = trie[trie[u].fail].children[i];
            }
        }
    }
}

void match(string s) {
    int p = 0;
    
    for (char c : s) {
        int u = c - 'a';
        p = trie[p].children[u];
        cnt[p]++;
    }
}

void topoSort() {
    queue<int> q;
    
    for (int i = 1; i <= idx; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        cnt[trie[u].fail] += cnt[u];
        inDegree[trie[u].fail]--;
        
        if (inDegree[trie[u].fail] == 0) {
            q.push(trie[u].fail);
        }
    }
}

int main() {
    int n;
    cin >> n;
    
    string patterns[n + 1];
    for (int i = 1; i <= n; i++) {
        cin >> patterns[i];
        insert(patterns[i], i);
    }
    
    build();
    
    string text;
    cin >> text;
    match(text);
    
    topoSort();
    
    for (int i = 1; i <= n; i++) {
        int p = 0;
        for (char c : patterns[i]) {
            int u = c - 'a';
            p = trie[p].children[u];
        }
        cout << cnt[p] << endl;
    }
    
    return 0;
}

易错点

⚠️ 注意：

  1. AC 自动机是 KMP 和 Trie 的结合
  2. 失配指针的构建是关键
  3. 匹配时要注意失配指针的跳转
  4. AC 自动机是字符串算法的高级内容