AC自动机需要自备两个前置技能:KMP和trie树。
不要看代码，先理解思路。都不复杂，不理解的可以看我前面的博客。
参考了很多网上的教程：https://www.cnblogs.com/hyfhaha/p/10802604.html
https://blog.csdn.net/qq_40816078/article/details/82186531

1、问题来源

ac自动机其实就是一种多模匹配算法，那么什么叫做多模匹配算法。

单模就是 一个大长字符串里 找 一个 单词
多模就是 一个大长字符串里 找 多个 单词

单模的问题 用 KMP 算法！

多模的问题 用 ac自动机！

单模就是给你一个单词，然后给你一个字符串，问你这个单词是否在这个字符串中出现过（匹配），这个问题可以用kmp算法在比较高效的效率上完成这个任务。
那么现在我们换个问题，给你很多个单词，然后给你一段字符串，问你有多少个单词在这个字符串中出现过，当然我们暴力做，用每一个单词对字符串做kmp,这样虽然理论上可行，但是时间复杂度非常之高，当单词的个数比较多并且字符串很长的情况下不能有效的解决这个问题，所以这时候就要用到我们的ac自动机算法了。

KMP是用于一对一的字符串匹配，即在母串中寻求一个模式串的匹配

trie虽然能用于多模式匹配，但是每次匹配失败都需要进行回溯，如果模式串很长的话会很浪费时间

2、核心算法思路

ac自动机，就是在tire树的基础上，增加fail指针，如果当前点匹配失败，则将指针转移到fail指针指向的地方，这样就不用回溯，而可以一路匹配下去了。

3、算法示例

给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。

注意：是出现过，就是出现多次只算一次。

3.1 建立Trie树

我们将n个模式串建成一颗Trie树，建树的方式和建Trie完全一样。

3.2 构造fail指针

如何确定fail指针？？
重点：如果一个点 X 的Fail指针指向 Y 。root到Y的字符串 是 root到X的字符串 的一个后缀。
重点：如果一个点 X 的Fail指针指向 Y 。root到Y的字符串 是 root到X的字符串 的一个后缀。
重点：如果一个点 X 的Fail指针指向 Y 。root到Y的字符串 是 root到X的字符串 的一个后缀。

3.2.1构造第一步

把所有第一层的节点的 fail指针指向 root

3.2.2构造第二步

用BFS（广度优先遍历）方法把其他层的节点，逐层 构造 fail指针

说一下构造的思路
重点：如果一个点 X 的Fail指针指向 Y 。root到Y的字符串 是 root到X的字符串 的一个后缀。
举一个例子：
root到5C 的串 是 BC ，root到 3C的 串 是 C
root到7C 的后缀 包括：ABC、BC、C
则 7C的 fail指针应该指向 交集 最长 的那个。即，5C。因为他们都有BC的交集。

后面的以此类推：
4B 可以指向2B。root到2B的 串 是 B。root到4B的后缀包括：AB、B。有交集。所以可以指向。
5C 只能指向 3C，他们有交集 是 C
6D 只能指向root. 6D和8D没有交集. root到8D的 串 是 BCD,root到6D的后缀 包括：BD、D。没有交集。
8D 只能指向root。8D和6D没有交集，6D的 串 是 BD，root到8D的后缀包括：BCD、CD、D。没有交集的 都指向root。

void getFail(){
	for(int i=0;i<26;i++)trie[0].son[i]=1;			//初始化0的所有儿子都是1
	q.push(1);trie[1].fail=0;				//将根压入队列
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<26;i++){				//遍历所有儿子
			int v=trie[u].son[i];			//处理u的i儿子的fail，这样就可以不用记父亲了
			int Fail=trie[u].fail;			//就是fafail，trie[Fail].son[i]就是和v值相同的点
			if(!v){trie[u].son[i]=trie[Fail].son[i];continue;}	//不存在该节点，第二种情况
			trie[v].fail=trie[Fail].son[i];	//第三种情况，直接指就可以了
			q.push(v);						//存在实节点才压入队列
		}
	}
}

开始检索

为了避免重复计算，我们每经过一个点就打个标记为?1，下一次经过就不重复计算了。

同时，如果一个字符串匹配成功，那么他的Fail也肯定可以匹配成功（后缀嘛），于是我们就把Fail再统计答案，同样，Fail的Fail也可以匹配成功，以此类推……经过的点累加flag，标记为?1。

最后主要还是和Trie的查询是一样的。

int query(char* s){
	int u=1,ans=0,len=strlen(s);
	for(int i=0;i<len;i++){
		int v=s[i]-‘a‘;
		int k=trie[u].son[v];		//跳Fail
		while(k>1&&trie[k].flag!=-1){	//经过就不统计了
			ans+=trie[k].flag,trie[k].flag=-1;	//累加上这个位置的模式串个数，标记 已 经过
			k=trie[k].fail;			//继续跳Fail
		}
		u=trie[u].son[v];			//到儿子那,存在性看上面的第二种情况
	}
	return ans;
}

完整代码

#include<bits/stdc++.h>
#define maxn 1000001
using namespace std;
struct kkk{
	int son[26],flag,fail;
}trie[maxn];
int n,cnt;
char s[1000001];
queue<int >q;
void insert(char* s){
	int u=1,len=strlen(s);
	for(int i=0;i<len;i++){
		int v=s[i]-‘a‘;
		if(!trie[u].son[v])trie[u].son[v]=++cnt;
		u=trie[u].son[v];
	}
	trie[u].flag++;
}
void getFail(){
	for(int i=0;i<26;i++)trie[0].son[i]=1;			//初始化0的所有儿子都是1
	q.push(1);trie[1].fail=0;				//将根压入队列
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<26;i++){				//遍历所有儿子
			int v=trie[u].son[i];			//处理u的i儿子的fail，这样就可以不用记父亲了
			int Fail=trie[u].fail;			//就是fafail，trie[Fail].son[i]就是和v值相同的点
			if(!v){trie[u].son[i]=trie[Fail].son[i];continue;}	//不存在该节点，第二种情况
			trie[v].fail=trie[Fail].son[i];	//第三种情况，直接指就可以了
			q.push(v);						//存在实节点才压入队列
		}
	}
}
int query(char* s){
	int u=1,ans=0,len=strlen(s);
	for(int i=0;i<len;i++){
		int v=s[i]-‘a‘;
		int k=trie[u].son[v];		//跳Fail
		while(k>1&&trie[k].flag!=-1){	//经过就不统计了
			ans+=trie[k].flag,trie[k].flag=-1;	//累加上这个位置的模式串个数，标记已经过
			k=trie[k].fail;			//继续跳Fail
		}
		u=trie[u].son[v];			//到下一个儿子
	}
	return ans;
}
int main(){
	cnt=1;            //代码实现细节，编号从1开始
        scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%s",s);
		insert(s);
	}
	getFail();
	scanf("%s",s);
	printf("%d\n",query(s));
	return 0;
}

AC自动机理解

原文：https://www.cnblogs.com/duoba/p/13141136.html