AC自动机

2020-03-07

字数统计: 597字 | 阅读时长≈ 2分钟

AC自动机的总结

P3808 【模板】AC自动机（简单版）

1	#include<bits/stdc++.h>
2	using namespace std;
3	queue<int> q;
4	const int N = 500010;
5	struct AC_automaton
6	{
7	int c[N][26], val[N], fail[N], cnt;
8	//c数组记录字典树节点，val数组为该节点是否为字符串结尾（个数）（记录字符串结束的位置）， fail记录失配指针， cnt记录节点标号(对应val)
9	//cnt作用：模拟动态开点
10	void ins(char *s)//向字典树中插入字符串，s为模式串
11	{
12	int len = strlen(s); int now = 0;//从根节点0开始
13	for(int i = 0; i < len; i++)
14	{
15	int v = s[i] - 'a';//获取当前字符的值
16	if(!c[now][v])c[now][v] = ++cnt;//如果这个节点没开，则开点
17	now = c[now][v];//now移动到新节点，开始匹配下一个
18	}
19	val[now]++;//字符串插入完毕后在尾部打标记，val[u]表示以该点结尾的字符串个数
20	}
21	void build()//获取每个节点的失配指针
22	{
23	for(int i = 0; i < 26; i++)
24	if(c[0][i])fail[c[0][i]] = 0, q.push(c[0][i]);//首先将与根节点相连的点入队，即首字母入队，并赋失配指针为0
25	while(!q.empty())
26	{
27	int u = q.front(); q.pop();//出队
28	for(int i = 0; i < 26; i++)
29	{
30	if(c[u][i])fail[c[u][i]] = c[fail[u]][i], q.push(c[u][i]);//如果该节点存在，则他的失配指针为它的上一个失配指针处的失配指针，并入队
31	else c[u][i] = c[fail[u]][i];//该点不存在只更新fail指针
32	}
33	}
34	}
35	int query(char *s)//查询文本串中模式串的个数，s为文本串
36	{
37	int len = strlen(s); int now = 0, ans = 0;//ans记录答案（模式串个数），从根节点开始
38	for(int i = 0; i < len; i++)
39	{
40	now = c[now][s[i] - 'a'];//从当前节点向下走
41	for(int t = now; t && ~val[t]; t = fail[t])ans += val[t], val[t] = -1;//遍历该节点前失配指针，并统计个数，清楚val（避免重复统计）
42	}
43	return ans;
44	}
45	}AC;
46	int n;
47	char p[1000005];
48	int main()
49	{
50	scanf("%d", &n);
51	for(int i = 1; i <= n; i++)scanf("%s", p), AC.ins(p);
52	AC.build();
53	scanf("%s", p);
54	int ans = AC.query(p);
55	printf("%d\n", ans);
56	return 0;
57	}