要学会AC自动机，我们必须知道什么是Trie，也就是字典树。Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
一个常见的例子就是给出n个单词，再给出一段包含m个字符的文章，让你找出有多少个单词在文章里出现过。
----来自百度词条
大佬博客
https://bestsort.cn/2019/04/28/402/
https://www.cnblogs.com/cjyyb/p/7196308.html
https://blog.csdn.net/weixin_42146061/article/details/99584227
AC自动机算法分为3步：
1.构造一棵Trie树
2.构造失败指针
3.模式匹配
构造字典树上面讲过了
AC自动机的精髓是构造失配指针：
1.根节点所连接的第一层字母fail指针指向根节点！！！（划重点）
2.沿着trie上的字符串去构建，每次取出队列元素时，都要遍历26个字母，如果当前取出元素的子节点存在此字母，设为a，则a的失配指针指向父节点失配指针对应a的节点（是fail指针的子节点）
如下图，s的失配指针指向根节点，h指向其父节点失配指针的对应子节点
若不存在该子节点a，则让此点指向父节点失配指针对应a的节点(注意，不是失配指针指向该节点，而是trie树节点指向该节点)
为什么不存在此节点还要让他指向父节点失配指针的对应节点呢？，这是我刚学习的时候一直搞不懂的地方
看个例子，
3个模式串ab,ec，f;文本串abaec，问在文本串中出现几个模式串，output：2
红色是不存在的，为了方便理解（图在下面，旁边的数字表示字母编号）
当我们匹配文本串时，匹配完b节点，发现b节点不存在e，这个时候就可以转移到其父节点b的失配指针（为根节点）所指向的对应子节点e，于是可以继续匹配，如果不这样连接的话，就没法继续往下匹配了
我们假设一下没有连接的情况，即e不指向3，则查询到b时就卡住了，因为节点2并不存在e这个子节点
另外，记住AC自动机是多模式匹配算法，这样构建fail指针的目的是为了让匹配时可以一直在trie树上面跳
当前节点匹配失败时可以通过fail指针跳转到其他节点，不用回溯就可以一直匹配下去了
每个节点的失配指针所指向的深度永远是比i小的，因为fail所指向的是永远是后缀
1 void getFail(){
2 queue<int>q;
3 for(int i=0;i<26;++i){
4 if(tree[0].son[i]){
5 //括号里面那个是字母编号
6 tree[tree[0].son[i]].fail=0;//指向根节点
7 q.push(tree[0].son[i]); //入队
8 }
9 }
10 while(!q.empty()){
11
12 int now=q.front();
13 q.pop();
14 for(int i=0;i<26;++i){
15
16 if(tree[now].son[i]){
17
18 //指向他父亲节点所指向的节点----对应的子节点
19 //now是父亲节点，fail[now]则是父亲节点失配指针所指向的节点
20 //这里为什么要这样呢？
21 //此子节点连接上fail所指向的对应节点，可同时判断以当前匹配的文本串字母
22 // 为结尾的字符串有多少个 ，fail指向的节点永远是已匹配的字符串的后缀
23 tree[tree[now].son[i]].fail=tree[tree[now].fail].son[i];
24 q.push(tree[now].son[i]);
25 }
26 //不存在这个子节点
27 else //fail[tree[now].son[i]]=tree[fail[now]].son[i];
28
29 tree[now].son[i]=tree[tree[now].fail].son[i];
30 //当前节点的这个子节点指向
31 //父亲节点fail指针的这个子节点
32 }
33
34 }
35
36 }