AC自动机（Aho-Corasick Automation） 是以 Trie 作为结构基础，结合 KMP 的思想 建立的自动机，用于解决多模式匹配等任务。
简单的说，我们要对 Trie 上的每个状态 $u$ 构造一个失配指针（fail），指向状态 $v$ ，满足 $v$ 是 $u$ 的最长后缀。然后我们就可以像 KMP 算法那样，在 Trie 上完成多模式匹配任务。
建立AC自动机主要有两个步骤：
- 将所有模式串插入Trie中
- 利用KMP算法思想，对Trie上所有节点构造fail指针
而构造fail指针的具体过程也类似于KMP算法。我们使用bfs来实现fail指针的构建，考虑状态 $u$ ，设其通过字符 $c$ 的边指向状态 $v$ ，即$next(u,c) = v$ ，因为是bfs，所以我们可以保证$fail(u)$的fail指针一定已经被构建完毕 。如果 $u$ 可以接受字符 $c$ ，也就是状态$v$ 存在，那么直接可以令 $fail(v) = fail(next(fail(u),c))$；如果 $u$ 无法接受字符 $c$ ，即 $v$ 不存在，那么我们令 $next(u,c) = next(fail(u),c)$.特别的, $fail(0) = 0$。
建Trie树与构建fail指针部分的代码：
void insert(const string &s) {
int p=0;
for(auto c : s) {
if(!t[p].nxt[c-'a']) t[p].nxt[c-'a']=++tot;
p=t[p].nxt[c-'a'];
}
t[p].end+=1;
return;
}
void bfs() {
queue<int> q;
for(int i=0;i<26;i++) if(t[0].nxt[i]) q.push(t[0].nxt[i]);
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=0;i<26;i++) {
int &v=t[u].nxt[i];
if(v) t[v].fail = t[t[u].fail].nxt[i],q.push(v);
else v = t[t[u].fail].nxt[i];
}
}
}这样我们就完成了AC自动机的构建，时间复杂度为 $O(n| \sum |)$，其中 $| \sum |$ 为字符集大小。
我们发现，构建完AC自动机的Trie树实际上变成了一张图，也就是 字典图，并且原Trie树的边与新建的fail边分别构成了一棵树。在查询的时候，对于一个状态 $s$ ，我们从 $s$ 开始不断沿fail边向上跳，根据定义，fail边指向的每一个状态都可以与 $s$ 相匹配，所以只需要在跳的过程中不断累积答案，并将经过的状态打上标记。
int query(const string &s) {
int p=0,ans=0;
for(auto c : s) {
p=t[p].nxt[c-'a'];
for(int j=p;j && t[j].end != -1;j=t[j].fail) {
ans+=t[j].end;
t[j].end=-1;
}
}
return ans;
}下面我们再来看一个问题：
给你一个文本串 $S$ 和 $n$ 个模式串 $T_{1 \sim n}$，请你分别求出每个模式串 $T_i$ 在 $S$ 中出现的次数。
因为要统计次数，所以我们不能再在跳 fail 边时打标记了。如果每次都强行跳 fail 边，复杂度会退化到 $O(nm)$。那怎么办呢？我们要思考AC自动机的本质。我们每次统计答案，都是在将fail树的一条整链上的节点答案加一。我们可以用一些处理树上数据结构的技巧，只在起跳节点加上一，然后通过拓扑排序，将根节点的答案传递到子树中，这样就避免了反复跳 fail 边导致的复杂度退化。
void solve(string s) {
int p = 0;
for(auto c : s) {
p = t[p].nxt[c-'a'];
t[p].num++;
}
}
void topsort() {
queue<int> q;
for(int i=1;i<=tot;i++) if(!d[i]) q.push(i);
while(!q.empty()) {
int u=q.front();
q.pop();
for(auto id : t[u].v) ans[id] = t[u].num;
int v = t[u].fail;
t[v].num+=t[u].num;
if(!(--d[v])) q.push(v);
}
}此外，还可以通过子树求和的方法来优化复杂度，具体可查阅 oiwiki，此处暂略不提。