AC自动机

AC自动机是一种基于 Trie树 与 KMP 的解决多模式串匹配问题的算法。其实本质上是在 Trie 上跑 KMP。

先把每个每个模式串建到字典树上，然后手动去模拟一下匹配的过程。发现，当匹配一个串时，如果匹配失败，就做一个类似 KMP 要跳到另一个地方重新匹配，我们要求解的就是要跳到哪里。

定义 $fail_i$ 表示 $i$ 这个点失配后应该跳到的点的编号，$T_i$ 表示 Trie 上编号为 $i$ 的节点，$fa_x$ 表示节点 $x$ 的父亲。则如果 $i$ 的父节点 $fa_i$ 的 $fail$，也就是 $fail_{fa_i}$，满足 $fail_{fa_i}$ 这个点的子节点中有 $i$ 这个节点的字符，那么 $fail_i$ 指向这个子节点，也就是 $fail_i=x$ 满足 $T_x=T_i$ 且 $fa_x=fail_{fa_i}$；否则 $fail_i$ 指向根节点，也就是 $fail_i=0$。 求 $fail$ 的过程，可以用 bfs 按字典树的层序遍历。 定义 $ch_{p,u}$ 代表第 $p$ 个节点的 $u$ 个儿子是谁。 先把第一层的节点入队，也就是遍历 $26$ 个字母，满足 $ch_{0,i}$ 是有节点的，把它入队。 然后跑正常广搜，把队头 $p$ 取出来，每一个节点，遍历 $26$ 个字母，如果 $ch{p,i}$ 是有节点的，那么根据定义，得出 $fail_{ch_{p,i}}=ch_{fail_p,i}$，也就是以 $p$ 为父节点，满足有这个字符就更新 $fail$，把当前阶段 $ch_{p,i}$ 的 $fail$ 更新为父节点 $p$ 的 $fail$ 到 $i$ 的字符；如果没有这个节点，就进行一个记忆化的操作，让 $ch_{p,i}=ch_{fail_p,i}$ 把这个点连上。

把每个点的 $fail$ 处理出来之后，就是查询部分了。

查询的方法很简单，就是跑文本串，每个节点往下跑，匹配就走，没匹配就跳 $fail$，最后统计有多少个是单词的结尾。

具体实现如下： 先初始化遍历的指针 $p=0$ 在根节点，然后跑文本串，让 $p$ 取到这一个节点的数，也就是 $ch_{p,x}$，其中 $x=s_i-97$，然后跑这棵树。$j$ 从 $p$ 开始，当 $j$ 没有爬到根，也就是 $j\neq 0$ 时，且当前节点的 $cnt_j$ 是没计算过的，就让 $ans+cnt_j$，然后把 $cnt_j$ 标记为 $-1$，这里标记为 $-1$ 是因为如果标记为 $0$ 的话，有时可能会少统计。 最后 $ans$ 就是答案。

拓扑排序优化

AC自动机有一个非常牛的技巧，叫做拓扑排序优化。

AC自动机如果每次暴力跳 fail 的话，在一些类似“金字塔”的数据，也就是每个字符一样，第一个模式串长度是 $1$，第二个是 $2$，以此类推。在这样的数据中，如果每次都暴力跳 fail 的话，就会被卡成 $O(n^2)$ 导致超时。

在建 fail 时，把 fail 连成边，变成一棵 fail 树。所以可以将问题转换：在 fail 树上求链的长度。 在这时，有一个优化方法，就是用拓扑排序中的拓扑序来跑这个树。 在建 $fail$ 的过程中，如果没有这个节点，就进行一个记忆化的操作，让 $ch_{p,i}=ch_{fail_p,i}$ 把这个点连上。这其实就是一个建字典图的过程。 因为如果跑一个都是一个字符的链的 fail，会发现每次一个节点的结果上传，上面的数都会增加。所以可以从最底部开始向上做一个类似前缀和或者拓扑排序 DP 的操作，将子树的 cnt 向上传递。时间复杂度优化为严格 $O(n)$。

实现其实非常简单。拓扑排序的入度统计在建 $fail$ 时，在满足有边时把 $fail_{ch_{p,i}}$ 的入度加 $1$ 即可。 注意在建字典树时，在跑完模式串之后不需要更新 $cnt[p]$，只用 $ed_{id}=p$，其中 $ed_i$ 表示在第 $i$ 个单词结尾的编号，$id$ 在建树时把 $i$ 顺便传进来就可以。 那 $cnt$ 在哪更新呢？就要在写一个 $query$，其实本质上就是一个遍历。跑文本串，把当前这位的字符在字典树上的节点的 $cnt$ 加 $1$ 即可。 拓扑排序的过程和板子差不多，先将 $idx$ 个节点的字典树（其实是图）上的节点判断是不是入度为 $0$，如果是就入队。然后就是一个广搜的过程，在取出队头之后，将上面的节点拿到下面的节点的 $cnt$，也就是 $cnt_{fail_p}$ 加上 $cnt_p$，再让 $fail_p$ 这个节点的入度减 $1$。当 $cnt_{fail_p}$ 为 $0$ 时，就把它入队。

最后第 $i$ 个模式串的出现次数就是 $cnt_{ed_i}$。 注意点 1.注意在 bfs 时当满足 $ch_{p,i}\ge 0$ 时，处理完 $fail$ 之后要把 $ch_{p,i}$ 入队。 2.查询时 $cnt_j$ 统计完之后一定是标记为 $-1$，循环时的条件就是 $\sim cnt_j$，因为 $-1$ 的按位取反是 $0$。 3.注意字典树的建树操作时不要更新 $cnt$。 4.注意建 fail 和拓扑排序时更新入度的点，哪个是 $to$，哪个是 $from$。 5.注意要先跑 $query$ 再跑拓扑排序。

求主串中模式串出现次数(暴力跳fail)

P3808 AC 自动机（简单版）的代码。

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char s[N];
int ch[N][26];
int n;
int cnt[N],idx;
int fail[N];
char c[N];
void insert(char *c){
	int p=0;
	for(int i=0;c[i];i++){
		int x=c[i]-'a';
		if(!ch[p][x])ch[p][x]=++idx;
		p=ch[p][x];
	}
	cnt[p]++;
}
void bfs(){
	queue<int>q;
	for(int i=0;i<26;i++){
		if(ch[0][i]){
			q.push(ch[0][i]);
		}
	}
	while(q.size()){
		int p=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(ch[p][i]){
				fail[ch[p][i]]=ch[fail[p]][i];
				q.push(ch[p][i]);
			}
			else {
				ch[p][i]=ch[fail[p]][i];
			}
		}
	}
}
int query(){
	int ans=0;
	int p=0;
	for(int i=0;s[i];i++){
		p=ch[p][s[i]-'a'];
		for(int j=p;j&&~cnt[j];j=fail[j]){
			ans+=cnt[j];
			cnt[j]=-1;
		}
	}
	return ans;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%s",c);
		insert(c);
	}
	bfs();
	scanf("%s",s);
	cout<<query();
	return 0;
}

求每个模式串在主串中出现的次数(拓扑排序优化)

P5357 【模板】AC 自动机 的代码。

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int ch[N][30];
char s[N];
char str[N];
int n;
int fail[N];
int rd[N];
int cnt[N],ed[N];
int idx;
void insert(char *c,int id){
	int p=0;
	for(int i=0;c[i];i++){
		int x=c[i]-'a';
		if(!ch[p][x])ch[p][x]=++idx;
		p=ch[p][x];
	}
	ed[id]=p;
}
void bfs(){
	queue<int>q;
	for(int i=0;i<26;i++){
		if(ch[0][i]){
			q.push(ch[0][i]);
		}
	}
	while(q.size()){
		int p=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(ch[p][i]){
				fail[ch[p][i]]=ch[fail[p]][i];
				rd[fail[ch[p][i]]]++;
				q.push(ch[p][i]);
			}
			else {
				ch[p][i]=ch[fail[p]][i];
			}
		}
	}
}
void query(){
	int p=0;
	for(int i=0;s[i];i++){
		p=ch[p][s[i]-'a'];
		cnt[p]++;
	}
}
void topo(){
	queue<int>q;
	for(int i=1;i<=idx;i++){
		if(rd[i]==0)q.push(i);
	}
	while(q.size()){
		int p=q.front();
		q.pop();
		cnt[fail[p]]+=cnt[p];
		rd[fail[p]]--;
		if(rd[fail[p]]==0){
			q.push(fail[p]);
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%s",str);
		insert(str,i);
	}
	scanf("%s",s);
	bfs();
	query();
	topo();
	for(int i=1;i<=n;i++){
		cout<<cnt[ed[i]]<<'\n';
	}
	return 0;
}