AC自动机（二次加强）

看此文章前建议先看 字典树&AC自动机 理解相关知识。

AC自动机（二次加强）（拓扑优化）

P5357 【模板】AC自动机（二次加强版）

现在我们用 $abc$，$bc$，$b$ 来建一棵字典树，效果如下。（括号中的数为编号）

     根
    (0)
    /|\
   / | \
  /  |  \
 a   b   c
(1) (4) (6)
 |   |    \
 |   |     \
 b   c      *
(2) (5)
 |   |
 c   *
(3)
 |   
 * 

在我们建立完失配指针后，有编号 $3$ 指向 $5$，又有编号 $5$ 指向编号 $6$，在原来的AC自动机中，我们通过暴力跳失配指针来统计字符串出现的次数。不难发现遍历到编号 $3$ 时，要更新编号 $5$，$6$ 节点。遍历到编号 $5$ 时，又要更新编号 $6$ 。所以编号 $6$ 被更新了两遍。

当节点更多时，复杂度明显上升。所以我们可以用拓扑排序来解决。这时，遍历顺序为编号 $3$ 更新编号 $5$,编号 $5$ 更新编号 $6$。所有编号只会被遍历一次。

建立拓扑图

因为要有每个处理点的基本信息，即信息下传（这也是不用暴力查找的原因），所以字典树节点要多存一个出现次数的标记。

const int o_o=4e6+10;
struct po{//字典树节点 
	int s_m;//出现的次数 
	int f_l;//失配指针 
	int e_d;//结束指针 
	int s_n[26];//子节点 
}a_c[o_o];

可将失配指针看作有向连边，那么失配指针处理完后就是一个有向无环图。所以直接在遍历失配指针时，被指向的节点入度直接加一记录即可。

int i_n[o_o];//记录入度 
void g_f(){//处理失配指针 
	queue<int>q;
	for(int i=0;i<26;i++)//遍历根节点的儿子 
		if(a_c[0].s_n[i]){//有儿子 
			a_c[a_c[0].s_n[i]].f_l=0;//失配后回根节点 
			q.push(a_c[0].s_n[i]);//记录 
		}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(a_c[u].s_n[i]){
				a_c[a_c[u].s_n[i]].f_l=a_c[a_c[u].f_l].s_n[i];//这个节点的儿子的失配指针 指向 这个节点的失配指针指向的节点的儿子
				i_n[a_c[a_c[u].s_n[i]].f_l]++;//被指向的点入度 +1 
				q.push(a_c[u].s_n[i]);//压入队列 
			}else a_c[u].s_n[i]=a_c[a_c[u].f_l].s_n[i];//这个节点的失配指针指向的节点的儿子 是 这个节点的儿子
		}
	}
}

处理拓扑图

每回将入度为 $0$，的点遍历，因为遍历他们不会对结果产生影响（或者说没有节点再去改变它们的值）。

struct po{//字典树节点 
	int s_m;//出现的次数 
	int f_l;//失配指针 
	int e_d;//结束指针 
	int s_n[26];//子节点 
}a_c[o_o];
int i_n[o_o];//记录入度 
int x_n[o_o];//字符串出现的次数 
void g_f(){//处理失配指针 
	queue<int>q;
	for(int i=0;i<26;i++)//遍历根节点的儿子 
		if(a_c[0].s_n[i]){//有儿子 
			a_c[a_c[0].s_n[i]].f_l=0;//失配后回根节点 
			q.push(a_c[0].s_n[i]);//记录 
		}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(a_c[u].s_n[i]){
				a_c[a_c[u].s_n[i]].f_l=a_c[a_c[u].f_l].s_n[i];//这个节点的儿子的失配指针 指向 这个节点的失配指针指向的节点的儿子
				i_n[a_c[a_c[u].s_n[i]].f_l]++;//被指向的点入度 +1 
				q.push(a_c[u].s_n[i]);//压入队列 
			}else a_c[u].s_n[i]=a_c[a_c[u].f_l].s_n[i];//这个节点的失配指针指向的节点的儿子 是 这个节点的儿子
		}
	}
}

特殊处理

因为本题有重复字符串，所以可已将重复字符串编号指向同一个节点，这样既不影响节点状况，遍历的时候也有去重效果。

const int o_o=4e6+10;
struct po{//字典树节点 
	int s_m;//出现的次数 
	int f_l;//失配指针 
	int e_d;//结束指针 
	int s_n[26];//子节点 
}a_c[o_o];
string s;//字符串 
int x_p;//字典树节点编号 
int m_p[o_o];//处理重串 
void b_t(string s,int x){//建立字典树 
	int l=s.length();
	int n_w=0;//标号 0 为根节点 
	for(int i=0;i<l;i++){
		if(!a_c[n_w].s_n[s[i]-'a'])a_c[n_w].s_n[s[i]-'a']=++x_p;//点没出现过，赋予新编号 
		n_w=a_c[n_w].s_n[s[i]-'a'];
	}
	if(!a_c[n_w].e_d)a_c[n_w].e_d=x;//没出现过，标记 
	m_p[x]=a_c[n_w].e_d;//处理重串，重串本质上一样，只记录个“坐标”即可 
}

AC自动机（二次加强）代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
int r_r(){//快读 
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
const int o_o=4e6+10;
struct po{//字典树节点 
	int s_m;//出现的次数 
	int f_l;//失配指针 
	int e_d;//结束指针 
	int s_n[26];//子节点 
}a_c[o_o];
string s;//字符串 
int x_p;//字典树节点编号 
int m_p[o_o];//处理重串 
void b_t(string s,int x){//建立字典树 
	int l=s.length();
	int n_w=0;//标号 0 为根节点 
	for(int i=0;i<l;i++){
		if(!a_c[n_w].s_n[s[i]-'a'])a_c[n_w].s_n[s[i]-'a']=++x_p;//点没出现过，赋予新编号 
		n_w=a_c[n_w].s_n[s[i]-'a'];
	}
	if(!a_c[n_w].e_d)a_c[n_w].e_d=x;//没出现过，标记 
	m_p[x]=a_c[n_w].e_d;//处理重串，重串本质上一样，只记录个“坐标”即可 
}
int i_n[o_o];//记录入度 
void g_f(){//处理失配指针 
	queue<int>q;
	for(int i=0;i<26;i++)//遍历根节点的儿子 
		if(a_c[0].s_n[i]){//有儿子 
			a_c[a_c[0].s_n[i]].f_l=0;//失配后回根节点 
			q.push(a_c[0].s_n[i]);//记录 
		}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(a_c[u].s_n[i]){
				a_c[a_c[u].s_n[i]].f_l=a_c[a_c[u].f_l].s_n[i];//这个节点的儿子的失配指针 指向 这个节点的失配指针指向的节点的儿子
				i_n[a_c[a_c[u].s_n[i]].f_l]++;//被指向的点入度 +1 
				q.push(a_c[u].s_n[i]);//压入队列 
			}else a_c[u].s_n[i]=a_c[a_c[u].f_l].s_n[i];//这个节点的失配指针指向的节点的儿子 是 这个节点的儿子
		}
	}
}
void g_a_c(string s){//处理原串 
	int l=s.length();
	int n_w=0;
	for(int i=0;i<l;i++){
		n_w=a_c[n_w].s_n[s[i]-'a'];//顺着往下走 
		a_c[n_w].s_m++;//以这个节点结尾的字符串出现次数 +1 
	}
}
int x_n[o_o];//字符串出现的次数 
void t_p(){
	queue<int>q;
	for(int i=1;i<=x_p;i++)
		if(!i_n[i])q.push(i);//入度为 0 的点入队
	while(!q.empty()){
		int u=q.front();
		q.pop();
		x_n[a_c[u].e_d]=a_c[u].s_m;//保存这个字符串出现的次数 
		i_n[a_c[u].f_l]--;//这个节点指向的节点入度 -1 （这个点要被删去了） 
		a_c[a_c[u].f_l].s_m+=a_c[u].s_m;//出现的次数赋给被指向的对象（它包含了被指向对象的次数） 
		if(!i_n[a_c[u].f_l])q.push(a_c[u].f_l);//如果被指向的点没有别的点指它，就可以处理它了 
	}
}
int main(){
	int n=r_r();//读入长度
	for(int i=1;i<=n;i++){
		cin>>s;//读入字符串 
		b_t(s,i);//字符串建到字典树上
	}
	g_f();//处理失配指针 
	cin>>s;//读入查找串
	g_a_c(s);//在字典树上处理原串
	t_p();//拓扑排序统计答案 
	for(int i=1;i<=n;i++)printf("%d\n",x_n[m_p[i]]);
	return 0;
}

---

同样可以回刷一下 P3796 【模板】AC自动机（加强版）
只要稍微改一下就可以实现，可以用来复习巩固。

AC自动机（加强）代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
int r_r(){//快读 
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
const int o_o=1e6+10;
struct po{//字典树节点 
	int s_m;//出现的次数 
	int f_l;//失配指针 
	int e_d;//结束指针 
	int s_n[26];//子节点 
}a_c[o_o];
string s[o_o];//字符串 
int x_p;//字典树节点编号 
void yv(int k){
	memset(a_c[k].s_n,0,sizeof a_c[k].s_n);
	a_c[k].e_d=0;
	a_c[k].f_l=0; 
}
void b_t(string s,int x){//建立字典树 
	int l=s.length();
	int n_w=0;//标号 0 为根节点 
	for(int i=0;i<l;i++){
		if(!a_c[n_w].s_n[s[i]-'a']){
			a_c[n_w].s_n[s[i]-'a']=++x_p;//点没出现过，赋予新编号 
			yv(x_p);
		}
		n_w=a_c[n_w].s_n[s[i]-'a'];
	}
	a_c[n_w].e_d=x;
}
int i_n[o_o];//记录入度 
void g_f(){//处理失配指针 
	queue<int>q;
	for(int i=0;i<26;i++)//遍历根节点的儿子 
		if(a_c[0].s_n[i]){//有儿子 
			a_c[a_c[0].s_n[i]].f_l=0;//失配后回根节点 
			q.push(a_c[0].s_n[i]);//记录 
		}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(a_c[u].s_n[i]){
				a_c[a_c[u].s_n[i]].f_l=a_c[a_c[u].f_l].s_n[i];//这个节点的儿子的失配指针 指向 这个节点的失配指针指向的节点的儿子
				i_n[a_c[a_c[u].s_n[i]].f_l]++;//被指向的点入度 +1 
				q.push(a_c[u].s_n[i]);//压入队列 
			}else a_c[u].s_n[i]=a_c[a_c[u].f_l].s_n[i];//这个节点的失配指针指向的节点的儿子 是 这个节点的儿子
		}
	}
}
void g_a_c(string s){//处理原串 
	int l=s.length();
	int n_w=0;
	for(int i=0;i<l;i++){
		n_w=a_c[n_w].s_n[s[i]-'a'];//顺着往下走 
		a_c[n_w].s_m++;//以这个节点结尾的字符串出现次数 +1 
	}
}
struct pp{
	int i_d;
	int n_m; 
}a_s[o_o];//字符串出现的次数 
void t_p(){
	queue<int>q;
	for(int i=1;i<=x_p;i++)
		if(!i_n[i])q.push(i);//入度为 0 的点入队 
	while(!q.empty()){
		int u=q.front();
		q.pop();
		a_s[a_c[u].e_d].n_m=a_c[u].s_m;//保存这个字符串出现的次数 
		i_n[a_c[u].f_l]--;//这个节点指向的节点入度 -1 （这个点要被删去了） 
		a_c[a_c[u].f_l].s_m+=a_c[u].s_m;//出现的次数赋给被指向的对象（它包含了被指向对象的次数） 
		if(!i_n[a_c[u].f_l])q.push(a_c[u].f_l);//如果被指向的点没有别的点指它，就可以处理它了 
	}
}
bool cmp(pp a,pp b){//按题目要求排序 
	return a.n_m==b.n_m?a.i_d<b.i_d:a.n_m>b.n_m;
}
int main(){
	while(1){
		int n=r_r();//读入长度 
		if(!n)break;
		yv(0);
		for(int i=1;i<=n;i++){
			cin>>s[i];//读入字符串 
			a_s[i].i_d=i;
			a_s[i].n_m=0;
			b_t(s[i],i);//字符串建到字典树上 
		}
		a_c[0].f_l=0;
		g_f();//处理失配指针 
		cin>>s[0];//读入查找串 
		g_a_c(s[0]);//在字典树上处理原串 
		t_p();//拓扑排序统计答案 
		sort(a_s+1,a_s+1+n,cmp);//答案排序 
		cout<<a_s[1].n_m<<endl;//输出 
		cout<<s[a_s[1].i_d]<<endl;
		for(int i=2;i<=n;i++){
			if(a_s[i].n_m==a_s[i-1].n_m)cout<<s[a_s[i].i_d]<<endl;
			else break;
		}
	}
	
	return 0;
}