Time's Blog

Time的静态博客

0%

AC自动机

发表于 更新于 分类于

概述

AC自动机的目的是实现多模式串的匹配，即在一个主串中查询多个模式串
AC自动机是在trie(字典树)树的基础上实现的
对于一个主串，将这个各个模式串插入字典树，然后进行fail指针的生成fail指针的生成是AC自动机的关键
fail指针顾名思义就是在匹配失败时使用的，在匹配失败时下一步就是去fail指针指向的结点，避免了多次匹配造成的时间浪费

构建字典树

1
2
3
4
5
6
struct NODE
{
	int cnt;//字符串出现的次数
	int _next[26];//下一个字符
	int _fail;//失配指针
};
1
2
3
4
5
6
void node_init(int cnt)//初始化结点
{
	memset(node[cnt]._next, -1, sizeof(node[cnt]._next));
	node[cnt]._fail = -1;
	node[cnt].cnt = 0;
}

插入字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void insert_char(char *s)
{
	int p = 0;
	int len = strlen(s);
	int i;
	for(i=0;i<len;i++)
	{
		int t = s[i] - 'a';
		if (node[p]._next[t] == -1)//该节点不在字符串内
		{
			node_init(++num);
			node[p]._next[t] = num;
		}
		p = node[p]._next[t];
	}
	node[p].cnt++;//字符串出现次数++
}

失配指针的计算

对于一个结点C，假设它表示的字符是a，那么他的fail指针的计算就是沿着C的父节点的fail指针走，直到找到一个结点X，X有子节点T表示的字符也是a，那么fail指针就从结点C指向X的子节点T，找不到fail就指向根节点
特别的对于直接与根节点相连的结点
该过程可以用bfs实现
代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void cal_fail()
{
	queue<NODE>qu;
	int i;
	for(i=0;i<26;i++)
	{
		if (node[0]._next[i] != -1)
		{
			int t = node[0]._next[i];
			node[t]._fail = 0;//将与根结点直接相连的结点的fail指针置为0即指向根节点
			qu.push(node[t]);
		}
	}
	while (!qu.empty())
	{
		NODE temp = qu.front();
		qu.pop();
		for(i=0;i<26;i++)
		{
			if (temp._next[i] != -1)
			{
				int p = temp._fail;//父节点的fail指针
				while (p != -1 && node[p]._next[i] == -1)
				{
					p = node[p]._fail;
				}
				if (p == -1)//找不到
				{
					node[temp._next[i]]._fail = 0;
				} else if (node[p]._next[i] != -1)//找到符合要求的结点
					node[temp._next[i]]._fail = node[p]._next[i];
				qu.push(node[temp._next[i]]);
			}
		}
	}
}

查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void query()
{
	int len = strlen(ss);//ss为主串
	int i;
	int p = 0;
	for(i=0;i<len;i++)
	{
		int t = ss[i] - 'a';
		while (p != 0 && node[p]._next[t] == -1)//失配时顺着fail指针去查找
			p = node[p]._fail;
		p = node[p]._next[t];
		int temp;
		if (p != -1)
			temp = p;
		else
		{
			temp = p = 0;//没找到置为0
		}
		while (temp != 0 && node[temp].cnt != -1)//当前结点是一个模式字符串的结尾
		{
			ans += node[temp].cnt;
			node[temp].cnt = -1;//避免重复计算
			temp = node[temp]._fail;
		}
	}
}

例题：HDU 2222

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
#define wfor(i,j,k) for(i=j;i<k;++i)
#define mfor(i,j,k) for(i=j;i>=k;--i)
// void read(int &x) {
// 	char ch = getchar(); x = 0;
// 	for (; ch < '0' || ch > '9'; ch = getchar());
// 	for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
// }
const int maxn = 500005;
struct NODE
{
	int cnt;
	int _next[26];
	int _fail;
};
NODE node[maxn];
void node_init(int cnt);
void insert_char(char *s);
void query();
void cal_fail();
char ss[1000005];
int num;
int ans;
int main()
{
	std::ios::sync_with_stdio(false);
#ifdef test
	freopen("F:\\Desktop\\question\\in.txt", "r", stdin);
#endif
	int t;
	cin >> t;
	while (t--)
	{
		num = 0;
		ans = 0;
		node_init(0);
		int n;
		cin >> n;
		char tt[60];
		int i;
		wfor(i, 0, n)
		{
			cin >> tt;
			insert_char(tt);
		}
		cal_fail();
		cin >> ss;
		query();
		cout << ans << endl;
	}
	return 0;
}
void node_init(int cnt)
{
	memset(node[cnt]._next, -1, sizeof(node[cnt]._next));
	node[cnt]._fail = -1;
	node[cnt].cnt = 0;
}
void insert_char(char *s)
{
	int p = 0;
	int len = strlen(s);
	int i;
	wfor(i, 0, len)
	{
		int t = s[i] - 'a';
		if (node[p]._next[t] == -1)
		{
			node_init(++num);
			node[p]._next[t] = num;
		}
		p = node[p]._next[t];
	}
	node[p].cnt++;
}
void cal_fail()
{
	queue<NODE>qu;
	int i;
	wfor(i, 0, 26)
	{
		if (node[0]._next[i] != -1)
		{
			int t = node[0]._next[i];
			node[t]._fail = 0;
			qu.push(node[t]);
		}
	}
	while (!qu.empty())
	{
		NODE temp = qu.front();
		qu.pop();
		wfor(i, 0, 26)
		{
			if (temp._next[i] != -1)
			{
				int p = temp._fail;
				while (p != -1 && node[p]._next[i] == -1)
				{
					p = node[p]._fail;
				}
				if (p == -1)
				{
					node[temp._next[i]]._fail = 0;
				} else if (node[p]._next[i] != -1)
					node[temp._next[i]]._fail = node[p]._next[i];
				qu.push(node[temp._next[i]]);
			}
		}
	}
}
void query()
{
	int len = strlen(ss);
	int i;
	int p = 0;
	wfor(i, 0, len)
	{
		int t = ss[i] - 'a';
		while (p != 0 && node[p]._next[t] == -1)
			p = node[p]._fail;
		p = node[p]._next[t];
		int temp;
		if (p != -1)
			temp = p;
		else
		{
			temp = p = 0;
		}
		while (temp != 0 && node[temp].cnt != -1)
		{
			ans += node[temp].cnt;
			node[temp].cnt = -1;
			temp = node[temp]._fail;
		}
	}
}

本文标题:AC自动机

文章作者:Time

发布时间:2018年12月17日 - 20:12

最后更新:2019年03月06日 - 21:03

原始链接:http://startcraft.cn/post/5c28c80e.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

-------------The End-------------