AC 自动机是 trie 的存储加上 KMP 的思想。KMP 是解决 1 文本串 + 1 模式串 的匹配问题，AC 自动机则用来解决多个模式串的问题。和 KMP 一样，AC 自动机的时间复杂度也是 \(O(|t|)\) 的。
模型：给定文本串 \(T\) 和 \(n\) 个模式串 \(\{S_n\}\)，求：
- 在 \(T\) 中出现过的模式串有几个
- 所有模式串在 \(T\) 中的出现次数之和
AC 自动机的构成
- 一棵字典树
- \(fail\) 数组（对应 KMP 的 \(next\) 数组），是失配指针
\(fail\) 数组
建 AC 自动机首先要建立一棵字典树，并在字典树中插入所有的模式串。
假定现在有模式串 acat catalog tall all lac 和文本串 theresacataloglacatall，现在建立字典树之后：
\(fail_x\) 的定义是对于节点 \(x\)，从根节点到 \(x\) 的路径上的节点字符所组成的字符串的最长后缀（不包括本身），使得该后缀是一个模式串的前缀——这个前缀的结尾处在字典树上的编号。例如 catalog 的 L 的编号的 \(fail\) 就等于 tall 的 L 的编号。
Q1 如何建立 \(fail\) 数组
显然，字典树第一排的 A,C,T,L 的 \(fail=0(root)\)。将这些第一排的非空节点加入队列，做 BFS。伪代码：
while(队列非空)
取出队头←u
for v=0→25，则u的子节点为trie[u][v]
如果trie[u][v]存在
fail[trie[u][v]]=trie[fail[u]][v]
否则
trie[u][v]=trie[fail[u][v]]
解释：其实 \(fail\) 就是在你这边失配之后把你带到另一个串的一个位置使你不至于前功“尽”弃，这里就实现了这一效果，由于 \(fail_u\) 在 trie 中的深度一定比 \(u\) 小，因此在更新 \(fail_{trie[u][v]}\) 时，可以借用 \(fail_u\)，而我们知道一直到 \(u\) 和 \(fail_u\) 这两个前缀后缀都已经是匹配的了，这时 \(trie[u][v]\) 跟 \(trie[fail_u][v]\) 的字母又肯定是一样的，所以就可以实现继续的匹配，且一旦 \(trie[fail_u]\) 没有子节点 \(v\)，就肯定说明这个后缀再也找不到匹配的前缀了。这是有的同学可能会举一个反例，说假如这个后缀稍短一点的第二个匹配的前缀刚好有子节点 \(v\) 然而 \(fail_u\) 却没有，这个时候不是本应该 \(fail_{trie[u][v]}\) 不等于 0 吗？其实不然，如果真的存在这一种情况，那么 \(fail_u\) 节点就会在更新 \(u\) 的子节点之前（因为我们说了它的深度比 \(u\) 小）把自己的子节点 \(v\) 指向那个可以匹配的第二个 \(fail\) 了，这也就保证了 \(fail_{trie[u][v]}\) 永远不会漏掉一个可用的前缀。
这里做解释，\(fail\) 指针所连的边最后是会构成一棵树的，假如只看 \(fail\) 树，其实我们就是在逐层地树形 DP。至于 \(fail\) 树还能怎么用，犹待更新……
void get_fail(){
queue<int>q;
while(!q.empty())q.pop();
for(int i=0;i<26;i++)if(trie[0][i])fail[trie[0][i]]=0,q.push(trie[0][i]);
while(!q.empty()){
int now=q.front();q.pop();
for(int i=0;i<26;i++)
if(trie[now][i]){
fail[trie[now][i]]=trie[fail[now]][i];
q.push(trie[now][i]);
}
else
trie[now][i]=trie[fail[now]][i];
}
}
Q2 \(fail\) 数组有什么用
在真正的文本串匹配时，我们的思路是，一步一个脚印地将 \(T\) 的每一个字母依次循着 trie 往下走，就像一般的字典树一样，如果这个字符匹配上的不是空节点，那么就尝试在 \(fail\) 边到 \(fail\) 树根所组成的链上的所有 trie 节点 \(k\)，把 \(ans\)（记录最终答案的变量）加上 \(val_k\)（\(val_k\) 就是字典树记录单词末尾的标记，\(=0\) 说明不是单词结尾，\(=1\) 说明是）。
int query(string t){
int n=t.length(),root=0,ans=0;
for(int i=0;i<n;i++){
for(int j=trie[root][t[i]-'a'];j&&mark[j]>=0;j=fail[j])
ans+=mark[j],mark[j]=-1;
root=trie[root][t[i]-'a'];
}
return ans;
}
注：代码针对“模型”中的第一问，第二问同理，去掉 mark[j]>=0 的限制条件即可。
完整代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int trie[N][26],ord=0,mark[N],fail[N];
string s[N],t;
void insert(string s){
int n=s.length(),root=0;
for(int i=0;i<n;i++){
if(trie[root][s[i]-'a'])root=trie[root][s[i]-'a'];
else root=trie[root][s[i]-'a']=++ord;
}
mark[root]++;
}
void init(){
queue<int>q;
while(!q.empty())q.pop();
for(int i=0;i<26;i++)if(trie[0][i])fail[trie[0][i]]=0,q.push(trie[0][i]);
while(!q.empty()){
int now=q.front();q.pop();
for(int i=0;i<26;i++)
if(trie[now][i]){
fail[trie[now][i]]=trie[fail[now]][i];
q.push(trie[now][i]);
}
else
trie[now][i]=trie[fail[now]][i];
}
}
int query(string t){
int n=t.length(),root=0,ans=0;
for(int i=0;i<n;i++){
for(int j=trie[root][t[i]-'a'];j&&mark[j]>=0;j=fail[j])
ans+=mark[j],mark[j]=-1;
root=trie[root][t[i]-'a'];
}
return ans;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>s[i],insert(s[i]);
init();
cin>>t;
cout<<query(t)<<endl;
}
时间复杂度
对于第一问，以上代码的时间复杂度是严格 \(O(|T|+\Sigma |S|)\) 的，但如果要统计出现次数，\(fail\) 树上的每个节点不一定只访问一次，复杂度将不能保证。至于正确的做法，（转载）参见 ouuan 的博客：【模板】AC自动机（二次加强版）题解。