AC 自动机

参考资料

AC 自动机 - OI Wiki

例题

洛谷 P3808 AC 自动机（简单版）

给定 $n$ 个模式串 $s_i$ 和一个文本串 $t$ ，求有多少个不同的模式串在文本串里出现过。两个模式串不同当且仅当他们编号不同。

代码（1）

#include <bits/stdc++.h>
using namespace std;

const int N=1000005;
const int M=26;
int T[N][M],fail[N],vis[N];
int cnt=0,tmp=0;
int insert(string s)
{
	int u=0;
	for(auto c:s)
	{
		int &v=T[u][c-'a'];
		if(!v)v=++cnt;
		u=v;
	}
	if(!vis[u])vis[u]=++tmp;
	return u;
}
vector<int> G[N];
void build()
{
	queue<int> q;
	for(int i=0;i<M;i++)
	{
		if(!T[0][i])continue;
		q.push(T[0][i]);
		G[0].push_back(T[0][i]);
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<M;i++)
		{
			int &v=T[u][i],w=T[fail[u]][i];
			if(!v){v=w;continue;}
			fail[v]=w;
			G[w].push_back(v);
			q.push(v);
		}
	}
}
int sum[N],id[N];
void query(string s)
{
	int u=0;
	for(auto c:s)
	{
		u=T[u][c-'a'];
		sum[u]++;
	}
}
void dfs(int u)
{
	for(auto v:G[u])
	{
		dfs(v);
		sum[u]+=sum[v];
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		id[i]=insert(s);
	}
	build();
	string s;
	cin>>s;
	query(s);
	dfs(0);
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(sum[id[i]])ans++;
	}
	cout<<ans<<'\n';
	return 0;
}

洛谷 P3796 AC 自动机（简单版 II）

有 $N$ 个由小写字母组成的模式串以及一个文本串 $T$ 。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串 $T$ 中出现的次数最多。

代码（1）

#include <bits/stdc++.h>
using namespace std;

const int N=1000005;
const int M=26;
int T[N][M],fail[N],vis[N];
int sum[N],id[N];
int cnt=0,tmp=0;
vector<int> G[N];
void init()
{
	for(int i=0;i<=cnt;i++)
	{
		memset(T[i],0,sizeof T[i]);
		fail[i]=vis[i]=sum[i]=id[i]=0;
		G[i].clear();
	}
	cnt=tmp=0;
}
int insert(string s)
{
	int u=0;
	for(auto c:s)
	{
		int &v=T[u][c-'a'];
		if(!v)v=++cnt;
		u=v;
	}
	if(!vis[u])vis[u]=++tmp;
	return u;
}
void build()
{
	queue<int> q;
	for(int i=0;i<M;i++)
	{
		if(!T[0][i])continue;
		q.push(T[0][i]);
		G[0].push_back(T[0][i]);
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<M;i++)
		{
			int &v=T[u][i],w=T[fail[u]][i];
			if(!v){v=w;continue;}
			fail[v]=w;
			G[w].push_back(v);
			q.push(v);
		}
	}
}
void query(string s)
{
	int u=0;
	for(auto c:s)
	{
		u=T[u][c-'a'];
		sum[u]++;
	}
}
void dfs(int u)
{
	for(auto v:G[u])
	{
		dfs(v);
		sum[u]+=sum[v];
	}
}
string s[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	while(cin>>n&&n)
	{
		for(int i=1;i<=n;i++)
		{
			cin>>s[i];
			id[i]=insert(s[i]);
		}
		build();
		string t;
		cin>>t;
		query(t);
		dfs(0);
		int mx=0;
		for(int i=1;i<=n;i++)
		{
			mx=max(mx,sum[id[i]]);
		}
		cout<<mx<<'\n';
		for(int i=1;i<=n;i++)
		{
			if(mx==sum[id[i]])cout<<s[i]<<'\n';
		}
		init();
	}
	return 0;
}

洛谷 P5357 【模板】AC 自动机

给你一个文本串 $S$ 和 $n$ 个模式串 $T_{1 \sim n}$ ，请你分别求出每个模式串 $T_i$ 在 $S$ 中出现的次数。

代码（1）

#include <bits/stdc++.h>
using namespace std;

const int N=200005;
const int M=26;
int T[N][M],fail[N],vis[N];
int cnt=0,tmp=0;
int insert(string s)
{
	int u=0;
	for(auto c:s)
	{
		int &v=T[u][c-'a'];
		if(!v)v=++cnt;
		u=v;
	}
	if(!vis[u])vis[u]=++tmp;
	return u;
}
vector<int> G[N];
void build()
{
	queue<int> q;
	for(int i=0;i<M;i++)
	{
		if(!T[0][i])continue;
		q.push(T[0][i]);
		G[0].push_back(T[0][i]);
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<M;i++)
		{
			int &v=T[u][i],w=T[fail[u]][i];
			if(!v){v=w;continue;}
			fail[v]=w;
			G[w].push_back(v);
			q.push(v);
		}
	}
}
int sum[N],id[N];
void query(string s)
{
	int u=0;
	for(auto c:s)
	{
		u=T[u][c-'a'];
		sum[u]++;
	}
}
void dfs(int u)
{
	for(auto v:G[u])
	{
		dfs(v);
		sum[u]+=sum[v];
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		id[i]=insert(s);
	}
	build();
	string s;
	cin>>s;
	query(s);
	dfs(0);
	for(int i=1;i<=n;i++)
	{
		cout<<sum[id[i]]<<'\n';
	}
	return 0;
}

参考资料​

例题​

洛谷 P3808 AC 自动机（简单版）​

洛谷 P3796 AC 自动机（简单版 II）​

洛谷 P5357 【模板】AC 自动机​

参考资料

例题

洛谷 P3808 AC 自动机（简单版）

洛谷 P3796 AC 自动机（简单版 II）

洛谷 P5357 【模板】AC 自动机