AC自动机模板-Toy模板网

这篇具有很好参考价值的文章主要介绍了AC自动机模板。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'

using namespace std;

typedef long long ll;

const int N = 10010 * 50, M = 1000010;

int tr[N][26], cnt[N], idx;
char str[M];
int q[N], ne[N];

void insert()
{
	int p = 0;
	for(int i = 0; str[i]; i ++)
	{
		int t = str[i] - 'a';
		if(!tr[p][t])tr[p][t] = ++ idx;
		p = tr[p][t];
	}
	cnt[p] ++;
}

void build()
{
	int hh = 0, tt = -1;
	for(int i = 0; i < 26; i ++)
	{
		if(tr[0][i])q[++ tt] = tr[0][i];
	}
	
	while(hh <= tt)
	{
		int t = q[hh ++];//i-1
		for(int i = 0; i < 26; i ++)//p[i]
		{
			int c = tr[t][i];//i
			if(!c)continue;
			
			int j = ne[t];
			while(j && !tr[j][i])j = ne[j];
			if(tr[j][i])j = tr[j][i];
			
			ne[c] = j;
			q[++ tt] = c;
		}
	}
}

void solve()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i ++)
	{
		cin >> str;
		insert();
	}
	
	build();
	
	int ans = 0;
	cin >> str;
	for(int i = 0, j = 0; str[i]; i ++)
	{
		int t = str[i] - 'a';
		while(j && !tr[j][t])j = ne[j];
		if(tr[j][t])j = tr[j][t];
		
		int p = j;
		while(p && cnt[p] != -1)
		{
			ans += cnt[p];
			cnt[p] = -1;
			p = ne[p];
		}
	}
	cout << ans << endl;
}

int main()
{
	IOS
	int _;
	cin >> _;
	while(_ --)
	{
		memset(tr, 0, sizeof tr);
		memset(cnt, 0, sizeof cnt);
		memset(ne, 0, sizeof ne);
		
		solve();
	}
	
	return 0;
}

核心思路是kmp的拓展，只是i++、j++什么的转换成了树的形式，初始化用bfs，每一点的初始化都是借助于该层以前的层进行的。

trie图优化：

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'

using namespace std;

typedef long long ll;

const int N = 10010 * 50, M = 1000010;

int tr[N][26], cnt[N], idx;
char str[M];
int q[N], ne[N];

void insert()
{
	int p = 0;
	for(int i = 0; str[i]; i ++)
	{
		int t = str[i] - 'a';
		if(!tr[p][t])tr[p][t] = ++ idx;
		p = tr[p][t];
	}
	cnt[p] ++;
}

void build()
{
	int hh = 0, tt = -1;
	for(int i = 0; i < 26; i ++)
	{
		if(tr[0][i])q[++ tt] = tr[0][i];
	}
	
	while(hh <= tt)
	{
		int t = q[hh ++];//i-1
		for(int i = 0; i < 26; i ++)//p[i]
		{
			/*
			int c = tr[t][i];//i
			if(!c)continue;
			
			int j = ne[t];
			while(j && !tr[j][i])j = ne[j];
			if(tr[j][i])j = tr[j][i];
			
			ne[c] = j;
			q[++ tt] = c;
			*/
			int p = tr[t][i];
			if(!p)tr[t][i] = tr[ne[t]][i];
			else
			{
				ne[p] = tr[ne[t]][i];
				q[++ tt] = p;
			}
		}
	}
}

void solve()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i ++)
	{
		cin >> str;
		insert();
	}
	
	build();
	
	int ans = 0;
	cin >> str;
	for(int i = 0, j = 0; str[i]; i ++)
	{
		int t = str[i] - 'a';
		/*
		while(j && !tr[j][t])j = ne[j];
		if(tr[j][t])j = tr[j][t];
		*/
		j = tr[j][t];
		
		int p = j;
		while(p && cnt[p] != -1)
		{
			ans += cnt[p];
			cnt[p] = -1;
			p = ne[p];
		}
	}
	cout << ans << endl;
}

int main()
{
	IOS
	int _;
	cin >> _;
	while(_ --)
	{
		memset(tr, 0, sizeof tr);
		memset(cnt, 0, sizeof cnt);
		memset(ne, 0, sizeof ne);
		
		solve();
	}
	
	return 0;
}

ne[t]是回溯一次，tr[ne[t]][i]直接记录好了它下一个点的位置，存在儿子就到儿子，没有儿子就是记录的回溯好的点。

每个点的ne都被计算了。

纯板子：

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'

using namespace std;

typedef long long ll;

const int N = 10010 * 50, M = 1000010;

int tr[N][26], cnt[N], idx;
char str[M];
int q[N], ne[N];

void insert()
{
	int p = 0;
	for(int i = 0; str[i]; i ++)
	{
		int t = str[i] - 'a';
		if(!tr[p][t])tr[p][t] = ++ idx;
		p = tr[p][t];
	}
	cnt[p] ++;
}

void build()
{
	int hh = 0, tt = -1;
	for(int i = 0; i < 26; i ++)
	{
		if(tr[0][i])q[++ tt] = tr[0][i];
	}
	
	while(hh <= tt)
	{
		int t = q[hh ++];//i-1
		for(int i = 0; i < 26; i ++)//p[i]
		{
			int c = tr[t][i];//i
			if(!c)continue;
			
			int j = ne[t];
			while(j && !tr[j][i])j = ne[j];
			if(tr[j][i])j = tr[j][i];
			
			ne[c] = j;
			q[++ tt] = c;
		}
	}
}

void solve()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i ++)
	{
		cin >> str;
		insert();
	}
	
	build();
	
	int ans = 0;
	cin >> str;
	for(int i = 0, j = 0; str[i]; i ++)
	{
		int t = str[i] - 'a';
		while(j && !tr[j][t])j = ne[j];
		if(tr[j][t])j = tr[j][t];
		
		int p = j;
		while(p && cnt[p] != -1)
		{
			ans += cnt[p];
			cnt[p] = -1;
			p = ne[p];
		}
	}
	cout << ans << endl;
}

int main()
{
	IOS
	int _ = 1;
	//cin >> _;
	while(_ --)
	{
		//memset(tr, 0, sizeof tr);
		//memset(cnt, 0, sizeof cnt);
		//memset(ne, 0, sizeof ne);
		
		solve();
	}
	
	return 0;
}

求每个单词出现次数的模板：

（这里是把每个单词都当成了匹配串，只有一个匹配串的话就把匹配串也insert一下，只有匹配串的insert过程中有f[p]++）文章来源地址https://www.toymoban.com/news/detail-811869.html

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'

using namespace std;

typedef long long ll;

const int N = 1000010;

int n;
int tr[N][26], f[N], idx;
char str[N];
int ne[N], q[N];
int id[210];

void insert(int x)
{
	int p = 0;
	for(int i = 0; str[i]; i ++)
	{
		int t = str[i] - 'a';
		if(!tr[p][t])tr[p][t] = ++ idx;
		p = tr[p][t];
		f[p] ++;//只有匹配串的insert过程中有f[p]++
	}
	id[x] = p;
}

void build()
{
	int hh = 0, tt = -1;
	for(int i = 0; i < 26; i ++)
		if(tr[0][i])
			q[++ tt] = tr[0][i];
			
	while(hh <= tt)
	{
		int t = q[hh ++];
		for(int i = 0; i < 26; i ++)
		{
			int p = tr[t][i];
			if(!p)tr[t][i] = tr[ne[t]][i];
			else
			{
				ne[p] = tr[ne[t]][i];
				q[++ tt] = p;
			}
		}
	}
}

int main()
{
	IOS
	cin >> n;
	for(int i = 0; i < n; i ++)
	{
		cin >> str;
		insert(i);
	}
	
	build();
	
	for(int i = idx - 1; i >= 0; i --)f[ne[q[i]]] += f[q[i]];
    //核心思路是每个前缀的后缀都加上这个前缀的数量，用拓扑序，insert过程是一个串一个串加的，所以倒着来就是拓扑序
	
	for(int i = 0; i < n; i ++)
	{
		cout << f[id[i]] << endl;
	}
	
	return 0;
}

到了这里，关于AC自动机模板的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！