AC自动机
简介
AC自动机是kmp的超级升级版
kmp是求出一个模式串在文本串里出现了几次
AC自动机可以求出一堆模式串在文本串里出现了多少次
思想
首先，众所周知，如果我们有很多个字符串我们可以利用trie树来压缩空间
我们这个AC自动机也是一样的，可以理解为在AC自动机上跑kmp
实现
构筑trie
这个没什么好讲的了吧。直接上代码~
void build(char a[]){ int len=strlen(a+1); int x=0; for(int i=1;i<=len;++i){ int c=a[i]-'a'; if(!t[x].ch[c]){ t[x].ch[c]=++tot; } x=t[x].ch[c]; } t[x].num++;} fail指针
这才是AC自动机的核心内容。
首先看看AC自动机的结构：
struct qwq{ int fail; int ch[26]; int num;}t[2000001];int tot; tot是节点数，除了多了一个fail以外与trie没有差别
这个fail很玄学。。。
比如一个节点i的fail即fail[i]，它指向的是与以当前节点为结尾的字符串的后缀的相同长度最长的一个字符串
比如说下面这幅图：
然后接下来看看它怎么构造。
先上代码：
void getfail(){//BFS获取fail指针 queue q; for(int i=0;i<26;++i){ if(t[0].ch[i]){ t[t[0].ch[i]].fail=0;//第一层直接指向根节点（很明显没有节点符合刚刚fail指针的那个条件） q.push(t[0].ch[i]); } } while(!q.empty()){ int u=q.front(); q.pop(); for(int i=0;i<26;++i){ if(t[u].ch[i]){//假如这个节点的儿子i存在 t[t[u].ch[i]].fail=t[t[u].fail].ch[i];//我们这个儿子i的fail就指向他爸爸的fail指针的儿子i //这么构造的原因是，前面u节点的fail已经与u的后缀有最长的相同字符串 //然后现在就是多扩展一个字符ch[i] //肯定还是符合这个特性 //假如没有这个节点，那就相当于指向根节点了 q.push(t[u].ch[i]); } else t[u].ch[i]=t[t[u].fail].ch[i];//否则的话我们就创立一个虚拟节点，这个节点就是u的儿子i //相当于把fail指向那里，方便下一次获取fail } }} 我们先随便搞一棵trie树吧：
然后第一层先指向根节点
第二层来开始广搜，那个代表ab的节点第一个被遍历到
然后指向那个代表b的节点
代表ac的节点同理指向代表c的节点
然后代表bc的节点也这样指向c
但是代表cd的节点没法指向d节点（d节点为0），只能指向根节点
然后之后的过程就可以自己推啦，我就直接上图了
那么到这里fail指针的构造就结束了
然后接下来就可以看看AC自动机的应用了
应用
洛谷P3808 【模板】AC自动机（简单版）
给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。
输入格式：
第一行一个n，表示模式串个数；
下面n行每行一个模式串；
下面一行一个文本串。
输出格式：
一个数表示答案
输入样例
2aaaaa
输出样例
2
题解
没什么好说的，板子题啊
我们对于模式串先构筑AC自动机
然后对于文本串，一位一位地去沿着fail指针跳，假如沿着fail指针跳出来的节点还没有被统计过，我们就加入到答案中
因为假如有一个模式串已经在文本串中出现过，那么它的fail指针这条链上的所有字符串肯定也出现过的
对于有没有被统计过的话可以赋特值
代码长下面这样：
#includeusing namespace std;struct qwq{ int fail; int ch[26]; int num;}t[2000001];int tot;void build(char a[]){ int len=strlen(a+1); int x=0; for(int i=1;i<=len;++i){ int c=a[i]-'a'; if(!t[x].ch[c]){ t[x].ch[c]=++tot; } x=t[x].ch[c]; } t[x].num++;}void getfail(){ queue q; for(int i=0;i<26;++i){ if(t[0].ch[i]){ t[t[0].ch[i]].fail=0; q.push(t[0].ch[i]); } } while(!q.empty()){ int u=q.front(); q.pop(); for(int i=0;i<26;++i){ if(t[u].ch[i]){ t[t[u].ch[i]].fail=t[t[u].fail].ch[i]; q.push(t[u].ch[i]); } else t[u].ch[i]=t[t[u].fail].ch[i]; } }}int query(char a[]){ int len=strlen(a+1); int x=0; int ans=0; for(int i=1;i<=len;++i){ int c=a[i]-'a'; x=t[x].ch[c]; for(int i=x;i&&t[i].num!=-1;i=t[i].fail){ ans+=t[i].num; t[i].num=-1; } } return ans;}char a[2000001];int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%s",a+1); build(a); } getfail(); scanf("%s",a+1); printf("%d\n",query(a));}