我们来讲讲AC自动机，单看这个名字我们恐怕还不知道这是用来干嘛得，但我们之前已经学了KMP以及trie树，我们知道KMP 大多是用来解决单串单串匹配的问题的，而AC自动机=KMP+trie树，AC自动机是一种多模匹配算法，AC自动机的关键是构建字典图实现自动跳转，构建 失配指针 实现多模式匹配。
首先AC自动机的建立需要一个Trie树 然后转化成Trie图 Trie图就是在每个tire树上的每个节点的所有分支(不论存不存在)连上一条接向树上其他节点的边接向的位置 要连到该前缀上一次匹配的点 找最优
所谓AC自动机就是在KMP的基础上 用来解决一大串里面的许多小串出现次数　出现位置 出现个数等问题的
本来想配图讲得但是尝试自己画图把整个过程拆分了下　才做了几张图就花了好长时间　所以最后还是决定上代码来说说

先说一下fail指针
如果当前点匹配失败,则将指针转移到fail指针指向的地方,这样就不用回溯,而可以路匹配下去了.(当前模式串后缀和fail指针指向的模式串部分前缀相同,如abce和bcd,我们找到c发现下一个要找的不是e,就跳到bcd中的c处,看看此处的下一个字符(d)是不是应该找的那一个)，一般,fail指针的构建都是用bfs实现的

简单介绍后　直入主题，因为之前讲trie树，其次AC自动机除了建树外多了个构建失配指针和匹配 我打算直接上代码配注释
#include <queue>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2*1e6+9;</algorithm></iostream></cstring></string></cstdio></cmath></cstdlib></queue>

int trie[maxn][26]; //字典树
int cntword[maxn]; //记录该单词出现次数
int fail[maxn]; //失败时的回溯指针
int cnt = 0;

void insert(string s)//不多讲 跟trie树基本一样
{
int root = 0;
for(int i=0;i<s.size();i++){
int next=s[i]-'a';
if(!trie[root][next])
trie[root][next]=++cnt;
root=trie[root][next];
}
cntword[root]++; //当前节点单词数+1
}

void getFail()//构造失配指针利用bfs 遍历
{
queue <int>q;// 队列存
for(int i=0;i<26;i++)
{ //将第二层所有出现了的字母扔进队列
if(trie[0][i])//若存在这个点
{
fail[trie[0][i]] = 0;//第二层都要指向根节点
q.push(trie[0][i]);//并将该结点编号压入队列
}
}</int>

//fail[now] ->当前节点now的失败指针指向的地方
////tire[now][i] -> 下一个字母为i+'a'的节点的下标为tire[now][i]
while(!q.empty())//遍历所有的结点
{
int now = q.front();//每次取出队头
q.pop();
for(int i=0;i<26;i++)
{ //查询26个字母，枚举所有可能的子结点（26个字母）
if(trie[now][i])//若存在这个字母的子结点
{
//如果有这个子节点为字母i+'a',则
//让这个节点的失败指针指向(((他父亲节点)的失败指针所指向的那个节点)的下一个节点)
fail[trie[now][i]] = trie[fail[now]][i];
q.push(trie[now][i]);//把该结点压入队列里等待继续往下遍历
}
else//否则就让当前节点的这个子节点
//指向当前节点fail指针的这个子节点
trie[now][i] = trie[fail[now]][i];
/因为不存在该结点，本身在trie树里会直接结束，但是会浪费时间
所以这里本身没有路可以走了，
但是这里让当前结点的子结点直接指向当前结点的失配指针fail指向的结点，
把路连上，下次遇上了可以直接走，这样将trie树构造成trie图，更加的优化、
其实就是相当于先预处理好，因为每一个点都要尽量连到另一个相同字母的结点，每一次遍历可能尽管这个结点没有这个字母
但是先把他连到结点的失配指针指向的那一个结点，说不定就有这个字母/
}
}
}

int query(string s)// AC自动机匹配
{
int now = 0,ans = 0;
for(int i=0;i<s.size();i++)
{ //遍历文本串
now = trie[now][s[i]-'a']; //从s[i]点开始寻找
for(int j=now;j && cntword[j]!=-1;j=fail[j])
{
//一直向下寻找,直到匹配失败(失败指针指向根或者当前节点已找过).
ans += cntword[j];
cntword[j] = -1; //标记已走过（已经加过一遍了）,防止重复计算
}
}
return ans;
}

int main() {
int n;
string s;
cin >> n;
for(int i=0;i<n;i++)
{
cin>>s;
insert(s);//建trie树（图）
}
fail[0]=0;//结束标志（根节点的失配指针是一定指向自己的）
getFail();//求出失配指针
cin>>s ;
cout<<query(s)<<endl;
return 0;
}

模板题　洛谷P3808