转载自yangrunze 的秘密小屋
我们仍未知道为什么一个PJ刚刚转TG的蒟蒻要学这个东西
也许，是因为这个算法的名字太美妙了吧
（如有错误，欢迎来踩）
AC自动机是啥？
是一个能够让你自动AC的算法
哦不对，是一个关于字符串匹配的算法
提到字符串匹配，大家应该都会想到KMP（既然来学AC自动机了，应该没有不知道的吧）
如果你听说过KMP，你应该对一个模式串匹配一个文本串的问题了如指掌
不过，对于多个模式串，好多好多个模式串呢？
你也许会想到对每个模式串都KMP一遍，但直觉告诉你，这样是不可能AC的
于是，AC自动机就派上用场了
当然，要学习AC自动机，你还需要掌握一种数据结构——
踹树
，啊呸，Trie树
而前面一直提的KMP，你只需要领会它的“利用匹配过程中得到的已知线索，来加快匹配速度”的思想就好啦，不需要掌握它的代码实现（当然，如果掌握了的话更好，会对接下来的学习更有帮助哦）
整个AC自动机分三步：建树与插入、构建fail边和匹配查询
1. 建树与插入
这个就是Trie树的基本操作啦，如果你已经把学过的Trie树的知识还给老师了，那正好借此机会来复习一下！
struct luogu{//Trie树结构体
int son[30];//Trie树的子节点
int cnt,fail;//cnt就是这个单词出现的次数（单词标记），至于这个fail一会再说
}trie[500010];
int tot=0;//节点编号
void insert(string s){//把一个字符串插入到Trie树里
int u=0;//从根节点开始（我们把根节点设为0号节点）
for(int i=0;s[i];i++){
int v=s[i]-'a';//当前的字母
if(!trie[u].son[v])//如果没找到这个节点，
trie[u].son[v]=++tot;//那就新开一个~
u=trie[u].son[v];//顺着往下找
}
trie[u].cnt++;//这个单词又出一遍，计数器++
}那么问题来了，我们这里为啥没有用单词末尾的标记end，而加了一个统计单词个数的cnt呢？这么问的绝对没认真读题，题目里有这一句：
管理员提示：本题数据内有重复的单词，且重复单词应该计算多次，请各位注意
这下就一目了然了吧~
2. 构建fail边
敲黑板，划重点啦！这一部分特别特别重要，是整个AC自动机的重点和难点所在，小伙伴们一定要竖起耳朵认真听！！
-
fail边的定义
首先，咱们插入这些模式串：
abc
bcd
bd
c
然后还有一个文本串：abcdbc
那么下面我们开始匹配啦！
从头开始，a，b，c，……哎呀！没了！
也就是说，到c这一块，失配了！
根据KMP的思想，我们可以接着找一个有"bc"的地方接过去匹配
那哪里有"bc"呢？哇！"bcd"这一块刚好有一个！
所以我们在把"abc"匹配完成之后，直接跳到"bcd"里的'c'这个节点，接着匹配就行啦
看到那条漂亮的紫色边没有？这就是传说中的fail边，之所以叫“fail边”，是因为它决定着这个字符串失配后的去向
那问题来了，右面"c"这个字符串里也有个c，为啥不和它连成fail边呢？
原因很简单，公共部分"bc"比公共部分"c"显然更有，咱们在KMP里求的不也是最长公共前后缀嘛，也许你已经发现了，这个fail边的作用，和KMP中的next数组是一样的！！！
也就是说：fail边指向的就是当前节点所在的字符串的最长后缀的最后一个字符
那你来找一下"bcd"中的'd'的fail边指向谁呢？
答案当然是"bd"中的'd'
那么"abc"中的"a"呢？
好像没有哎……没有，那就是指向根节点
这个图标出了所有节点的fail边，可能画的有点乱，不过只要弄清了fail边的定义，那就很好办啦！
-
fail边的代码实现
掌握了fail边的定义，接下来我们就要开始研究代码咋写了
首先，不难发现，第一层的fail边都是根节点
然后呢？找fail边应该这么找：
顺着你爸的fail边找上去，如果它指向的节点的孩子的字符和你的字符相等，那它的这个孩子就你要连的fail边
貌似有点复杂……咱还是拿刚才"abc"里的那个'c'举例子：
"abc"中的'c'的父节点是"abc"中的'b'
"abc"中的'b'的fail边是"bcd"中的'b'
"bcd"中的'b'正好有一个儿子'c'，那"abc"中的'c'就要把fail边连到那儿
那么有好奇的小朋友就要问了：如果你爸没你这个孩子，那该怎么办呢？
我们要大力发扬咱们的瞎搞精神：没有孩子，咱就给它造一个，把当前的孩子直接变成你爸的fail指针的孩子，直接跳到那里去匹配
也许你已经发现了，我们找fail边，是一层一层往下找的，所以找fail边的过程，实际上就是一个bfs的过程，需要借助队列来实现
void getfail(){//STL大法好！！！
queue<int>q;
for(int v=0;v<26;v++){//初始化第一层的fail边
int c=trie[0].son[v];
if(c){//如果有这个孩子
trie[c].fail=0;//那就把它的fail边指向根节点0
q.push(c);//并把它压入队列
}
}
while(!q.empty()){//开始bfs！
int u=q.front();//取队首（这个队首是爸爸，我们要用它更新孩子）
q.pop();//pop出去
int f=trie[u].fail;//找到你爸的fail边
for(int v=0;v<26;v++){//一个一个孩子去找
int c=trie[u].son[v];
if(c){//如果有这个孩子
trie[c].fail=trie[f].son[v];//根据刚才说的，连接fail边
q.push(c);//压入队列
}
else trie[u].son[v]=trie[f].son[v];//否则就“造”一个孩子
}
}
}3. 匹配查询
fail边都已经搞定了，匹配就是小case啦！
匹配的代码，其实和trie树的查找差不多，一个一个找下去，找到末尾
但这里有点不同，走到一个字符之后，咱们先去走它的fail边，走完之后再继续往下找（要不咱大费周章地找fail边意义何在？）
但要注意的是，题目让我们求有多少个模式串在文本串里出现过，所以出现过加完了cnt之后，咱们把cnt变成-1，下次遇到-1，就可以知道这个串已经统计过一遍了，就可以结束跳fail的过程，去找下一个节点了
int find(string s){//对文本串s进行匹配
int u=0;//当前节点
int sum=0;//统计答案
for(int i=0;s[i];i++){
int v=s[i]-'a';
int c=trie[u].son[v];//依旧是Trie树的查找过程
while(c&&trie[c].cnt!=-1){//如果这个节点不是根节点，而且还不是-1
sum+=trie[c].cnt;//加到答案里
trie[c].cnt=-1;//加过了，变成-1
c=trie[c].fail;//跳fail边
}
u=trie[u].son[v];//去往下一个节点
}
return sum;//这个就不用解释了吧
}完整代码：
//通过套取数据而直接“打表”过题者，是作弊行为，发现即棕名。
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
struct luogu{//Trie树
int son[30];
int cnt,fail;
}trie[500010];
int tot=0;
void insert(string s){//插入
int u=0;
for(int i=0;s[i];i++){
int v=s[i]-'a';
if(!trie[u].son[v])
trie[u].son[v]=++tot;
u=trie[u].son[v];
}
trie[u].cnt++;
}
void getfail(){//构建fail边
queue<int>q;
for(int v=0;v<26;v++){
int c=trie[0].son[v];
if(c){
trie[c].fail=0;
q.push(c);
}
}
while(!q.empty()){
int u=q.front();
q.pop();
int f=trie[u].fail;
for(int v=0;v<26;v++){
int c=trie[u].son[v];
if(c){
trie[c].fail=trie[f].son[v];
q.push(c);
}
else trie[u].son[v]=trie[f].son[v];
}
}
}
int find(string s){//匹配查询
int u=0;
int sum=0;
for(int i=0;s[i];i++){
int v=s[i]-'a';
int c=trie[u].son[v];
while(c&&trie[c].cnt!=-1){
sum+=trie[c].cnt;
trie[c].cnt=-1;
c=trie[c].fail;
}
u=trie[u].son[v];
}
return sum;
}
int main(){
int n;
string s;
cin>>n;
while(n--){
cin>>s;
insert(s);//将每个模式串插入到Trie树中
}
getfail();//构建fail边
cin>>s;
cout<<find(s);//对文本串进行匹配
return 0;//完美结束
}
最后说一下，AC自动机好虽好，但是不能滥用，否则会
这样
（伦敦大雾，AC自动机和自动AC机不是一个东西啦）