AC_自动机(并不会帮你自动ac题目)

2022-03-14

如题目＞▽＜

什么是AC自动机

Aho-Corasick automaton，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法。要学会AC自动机，我们必须知道什么是Trie，也就是字典树。Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

因此AC自动机可不是什么Accept automaton，并不会帮你自动AC

干啥用的

AC自动机用于多模式串匹配问题，例如给几个关键词（模式串），再给一篇文章，判断关键词是否在文章中出现，或出现的次数，有哪些关键词出现等等

前置知识

必须掌握Trie树
建议掌握KMP算法
先对模式串用Trie树进行构建，然后用BFS进行失陪指针的初始化
理论基础在这里看

基础AC自动机模板

以ac自动机模板题为例

namespace ac {
    int t = 0;
    int tr[MAX][26], e[MAX], fail[MAX];
    
    void insert(char *s) {
        int p = 0;
        for (int i = 0; s[i]; i++) {
            if (!tr[p][s[i] - 'a']) {
                tr[p][s[i] - 'a'] = ++t;
            }
            p = tr[p][s[i] - 'a'];
        }
        e[p]++;// 节点为p的字符串的个数
    }
    queue<int> q;
    void build() {
        for (int i = 0; i < 26; i++) {
            if(tr[0][i]) {// 最初的首字母入队
                q.push(tr[0][i]);
            }
        }
        while (!q.empty()) {
            int p = q.front();
            q.pop();
            for (int i = 0; i < 26; i++) {
                if (tr[p][i]) {
                    fail[tr[p][i]] = tr[fail[p]][i];// 有子节点，将子节点的fail指向父节点fail指向的节点
                    q.push(tr[p][i]);
                } else {
                    tr[p][i] = tr[fail[p]][i];// 无该子节点，将该子节点指向父节点fail指向的节点
                }
            }
        }
    }
    int query (char *s) {
        int p = 0, res = 0;
        for (int i = 0; s[i]; i++) {
            p = tr[p][s[i] - 'a'];
            for (int j = p; j > 0 && e[j] != -1; j = fail[j]) {
                res += e[j];
                e[j] = -1;
            }
        }
        return res;
    }
}
char s[MAX];
int main(){
    fast;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s;
        ac::insert(s);
    }
    cin >> s;
    ac::build();
    cout << ac::query(s);
    return 0;
}