标题怎么这么长啊？自动AC的机器？看起来好厉害。

然而实际上这个标题只是简述了AC自动机的实现方式——在Trie树上通过构建fail指针实现。它不能自动AC题目，甚至还有可能会让你收获一个WA。

那么AC自动机是一个什么东西呢？

AC自动机是一个用于字符串多模匹配的算法，它以Trie树为基础，结合KMP思想实现的。

它的构造过程如下：

1. 将所有模式串写入一个Trie树，构建基本数据结构。
2. 在Trie树上构建失配指针（fail指针），构建字典图。

然后我们就可以用它对目标串进行多模匹配了。

AC自动机的时间复杂度为$O(|S|+m)$，其中$|S|$为目标串长度，$m$为匹配次数。

• 如何去理解fail指针？

从该节点取前缀，在字典树中找到该前缀中后缀最长的节点。

这么一说可能既不严谨也不容易理解。我们不妨把KMP中的前缀数组思想拿过来类比。

我们都知道，在字符串模式匹配问题中最关键的问题就是拿已匹配的长度去减少回跳的量。在KMP算法中，我们引入前缀数组，通过计算公共最长前后缀达到这个效果。而在这里，我们通过构造fail指针，将回跳的量减少至前缀的位置。

读者可以参考尾部OI-Wiki中对这一部分内容的详细介绍。

• 字典图？

在参考代码的第39行，我们可以看到在AC自动机的构建过程中，我们对字典树进行了修改，使之形成了字典图。

这个过程，我们实际上是在做路径压缩。

在某一节点$u$，如果发生失配，很明显当前指针会跳回到$fail[u]$的位置，然而在这一节点可能仍然会失配，因此可能会发生多次跳转的情况。

我们通过将字典树修改为字典图，直接将字典树中fail指针跳转的位置修改到下一可以匹配的位置。

参考代码：

//luogu P3808
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 6;

int n;

namespace AC {
    int trie[MAXN][26];
    int e[MAXN];
    int cnt;
    int fail[MAXN];

    void add(char *s) {
        int p = 0;
        for ( int i = 1; s[i]; ++i ) {
            int c = s[i] - 'a';
            if ( !trie[p][c] )
                trie[p][c] = ++cnt;
            p = trie[p][c];
        }
        ++e[p];
    }

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

    int query(char *t) {
        int ret = 0;
        int u = 0;
        for ( int i = 1; t[i]; ++i ) {
            int c = t[i] - 'a';
            u = trie[u][c];
            for ( int j = u; j && e[j] != -1; j = fail[j] ) {
                ret += e[j];
                e[j] = -1;
            }
        }

        return ret;
    }
}

int main() {
    char s[MAXN];
    
    scanf("%d", &n);
    for ( int i = 1; i <= n; ++i ) {
        scanf("%s", s + 1);
        AC::add(s);
    }
    AC::build();

    scanf("%s", s + 1);
    printf("%d\n", AC::query(s));

    return 0;
}

参考资料：

https://oi-wiki.org/string/ac-automaton/