前言

想要理解一个算法，必然先要知道这个算法的用处。对于 AC 自动机而言，它的用处即是处理多模式串的文本串匹配问题（模式串即需要被统计出现次数等的字符串）。

算法分析

由于在文本串中，两个出现的模式串可能有重叠，即一个模式串的后缀会是另一个模式串的前缀。

而根据 KMP 算法带来的启发，我们也可以构造一个类似 next 数组的指针用于不同状态之间的转移。

在 AC 自动机中，我们称之为 fail，用于表示失配时从一个状态转移到另一个状态的过程。

考虑到有很多个模式串，我们可以用一棵 Trie 树来进行存储，则从根节点到每个节点的路径就表示某个或某些模式串的前缀。

接下来考虑构建 fail 指针。

首先，受 KMP 启发，fail 跳到的位置必然是当前位置代表的模式串的最长后缀，这样只要一直跳就能遍历到当前节点代表的字符串在树上的所有的后缀。

假设当前节点为 $u$，代表字符串 $S$，则若设 $S’$ 为在 $S$ 后加一个字符 $c$ 形成的字符串（即 trie[u][c] 代表 $S’$）

那么，若 trie[u][c] 存在，则 fail[trie[u][c]]=trie[fail[u]][c]（在 $u$ 和 $fail[u]$ 代表的字符串后都加上字符 $c$）；否则表示失配，trie[u][c]=trie[fail[u]][c]。此过程通过 BFS 即可完成。

为什么 trie[u][c] 存在时只需要跳一次呢？因为在之前的处理中，我们通过失配时的操作完成了类似路径压缩的操作，就无需进行 while 循环了。

洛谷 P3808 AC 自动机（简单版）

#include <bits/stdc++.h>
using namespace std;
int n,trans[1000005][30],tot,cnt[1000005],fail[1000005],ans;
string s,t;
queue<int> q;
void build_trie(string s){
    int p=0;
    for (int i=0;i<s.size();i++)
        if (trans[p][s[i]-'a']) p=trans[p][s[i]-'a'];
        else trans[p][s[i]-'a']=++tot,p=tot;
    cnt[p]++;
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        cin>>s;
        build_trie(s);
    }
    for (int i=0;i<26;i++) if (trans[0][i]) q.push(trans[0][i]);
    while (!q.empty()){
        int u=q.front(); q.pop();
        for (int i=0;i<26;i++)
            if (trans[u][i]) fail[trans[u][i]]=trans[fail[u]][i],q.push(trans[u][i]);
            else trans[u][i]=trans[fail[u]][i];
    }
    cin>>t;
    for (int i=0,p=0;i<t.size();i++){
        p=trans[p][t[i]-'a'];
        for (int j=p;j&&cnt[j]!=-1;j=fail[j]) ans+=cnt[j],cnt[j]=-1;
    }
    printf("%d\n",ans);
    return 0;
}