AC自动机

算法
字数统计: 1.7k   |   阅读时长≈ 8 分钟

基本介绍

AC自动机，正如他的名字，能够让你自动AC（误

其实是一个匹配字符串的算法。

简单来说，就是在trie树上用KMP的思想。

（当然，你也可以理解为就是用了KMP。。

因为本来trie树是可以用来匹配字符串的，但是因为匹配失败的时候都需要从头开始，会导致浪费了很多时间，加大了时间复杂度。

所以，就提出来了AC自动机。

原理就是和KMP的next数组类似，使用一个fail数组，来记录匹配失败之后，需要回溯到哪个地方。

这样便能减少很多复杂度。

时间复杂度为$O(n)$($n$为文本长度)

（AC自动机怎么不能帮助我自动AC啊。。

实现方式

1、建树

这里和trie树是一样的，我就不多赘述了。

1
2
3
4
5
6
7
8
9
10
11
12
const int N = 1e6 + 5;
int trie[N][30], cnt[N], fail[N], tot;

void insert(string s) {
	int len = s.length(),now = 0;
	for (int i = 0; i < len; i++) {
		int id = s[i] - 'a';
		if (!trie[now][id])	trie[now][id] = ++tot;
		now = trie[now][id];
	}
	cnt[now]++;
}

2、获取fail数组

这个fail数组就类似于KMP中的next数组，当你匹配失败的时候，能通过回溯的方式，来回到fail所指向的那个节点，通过这样的方式来减小时间复杂度。

而fail指针指向是与当前字符相同并且该字符所在的前缀构成现在字符的最长后缀。

用bfs的方式来获取fail数组。

这里以$aba,abcd,bca,bad$为例。

首先，第一层的节点的fail肯定是指向根节点的。

此外，对于遍历的节点来说。

如果遍历的节点存在指向的子节点的话，那么该子节点的fail为他的父节点的fail的节点指向相同节点的节点。

（有点绕啊。。不懂的看看代码吧。

如果遍历的节点不存在指向的子节点的话，那么令该节点指向他的fail的节点指向的相同节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Getfail() {
	queue<int>q;
	for (int i = 0; i < 26; i++)//第一层的直接指向根节点
		if(trie[0][i])
		fail[trie[0][i]] = 0, q.push(trie[0][i]);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = 0; i < 26; i++) {
			if (trie[now][i]) {//如果存在指向的子节点
				fail[trie[now][i]] = trie[fail[now]][i];
                //他子节点的fail为他的父节点，也就是now的fail的指向相同节点的节点
				q.push(trie[now][i]);
			}
			else trie[now][i] = trie[fail[now]][i];
            //如果不存在指向的子节点
            //那么直接让该节点指向他自己fail的节点的指向的相同节点
		}
	}
}

3、查询

从根节点开始一步步进行匹配。

1
2
3
4
5
6
7
8
9
10
int quiry(string s) {
	int now = 0, ans = 0, len = s.length();
	for (int i = 0; i < len; i++) {
		int id = s[i] - 'a';
		now = trie[now][id];
		for (int j = now; j && cnt[j] != -1; j = fail[j])//从now开始一直向下寻找，直到匹配失败（指向根节点或者已经被匹配过）
			ans += cnt[j], cnt[j] = -1;//将匹配过的节点进行标记
	}
	return ans;
}

4、last优化

不会last优化。。

这边记录一下，了解点击这里。

典型例题

1、HDU-2222 Keywords Search

题目大意

给你一串字符串，问你里面最多有多少个关键词。

解题思路

AC自动机模板题。

就是卡cin，cout。

真的难受。

完整代码

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <string>
using namespace std;

const int N = 1e6 + 5;
int trie[N][30], cnt[N], fail[N], tot;

void insert(string s) {
	int len = s.length(),now = 0;
	for (int i = 0; i < len; i++) {
		int id = s[i] - 'a';
		if (!trie[now][id])	trie[now][id] = ++tot;
		now = trie[now][id];
	}
	cnt[now]++;
}

void Getfail() {
	queue<int>q;
	for (int i = 0; i < 26; i++)
		if(trie[0][i])
		fail[trie[0][i]] = 0, q.push(trie[0][i]);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = 0; i < 26; i++) {
			if (trie[now][i]) {
				fail[trie[now][i]] = trie[fail[now]][i];
				q.push(trie[now][i]);
			}
			else trie[now][i] = trie[fail[now]][i];
		}
	}
}

int quiry(string s) {
	int now = 0, ans = 0, len = s.length();
	for (int i = 0; i < len; i++) {
		int id = s[i] - 'a';
		now = trie[now][id];
		for (int j = now; j && cnt[j] != -1; j = fail[j])
			ans += cnt[j], cnt[j] = -1;
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		tot = 0;
		memset(trie, 0, sizeof(trie));
		memset(fail, 0, sizeof(fail));
		memset(cnt, 0, sizeof(cnt));
		string s;
		for (int i = 0; i < n; i++) {
			cin >> s;
			insert(s);
		}
		Getfail();
		cin >> s;
		cout << quiry(s) << '\n';
	}
}

2、HDU-2896 病毒侵袭

题目大意

给你多个字符串，每个字符串按$1-M$编号，输入多个病毒特征码，按照$1-N$，问你每个字符串中存在的特征码。

解题思路

这个题目究极恶心，卡内存卡到吐。。

题目要求每个字符都是ASCII码可见字符（不包括回车）。

所以最大的就是$127-32=95$,我刚开始以为要开到128。

其他的就是模板了。

还要注意病毒的编号是从小到大输出的，可以用优先队列。

完整代码

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <functional>
#include <queue>
#include <string>
using namespace std;

const int N = 7e4 + 5;
int trie[N][100], cnt[N], fail[N], tot,flag[N];
priority_queue<int,vector<int>,greater<int>> ans;

void insert(string s,int g) {
	int len = s.length(), now = 0;
	for (int i = 0; i < len; i++) {
		int id = s[i] - ' ';
		if (!trie[now][id])	trie[now][id] = ++tot;
		now = trie[now][id];
	}
	cnt[now] = g;
}

void Getfail() {
	queue<int>q;
	for (int i = 0; i < 96; i++)
		if (trie[0][i])
			fail[trie[0][i]] = 0, q.push(trie[0][i]);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = 0; i < 96; i++) {
			if (trie[now][i]) {
				fail[trie[now][i]] = trie[fail[now]][i];
				q.push(trie[now][i]);
			}
			else trie[now][i] = trie[fail[now]][i];
		}
	}
}

void quiry(string s) {
	int now = 0, len = s.length();
	for (int i = 0; i < len; i++) {
		int id = s[i] - ' ';
		now = trie[now][id];
		for (int j = now; j && flag[j] != -1; j = fail[j]) {
			if (cnt[j] > 0)	ans.push(cnt[j]);
			flag[j] = -1;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	while (cin >> n) {
		tot = 0;
		memset(trie, 0, sizeof(trie));
		memset(fail, 0, sizeof(fail));
		memset(cnt, 0, sizeof(cnt));
		memset(flag, 0, sizeof(flag));
		string s;
		for (int i = 1; i <= n; i++) {
			cin >> s;
			insert(s, i);
		}
		Getfail();
		cin >> m;
		int c = 0;
		for (int i = 1; i <= m; i++) {
			cin >> s;
			quiry(s);
			if (!ans.empty()) {
				cout << "web " << i << ":";
				while (!ans.empty()) {
					cout <<" "<< ans.top();
					ans.pop();
				}
				cout << '\n';
				c++;
			}
			memset(flag, 0, sizeof(flag));
		}
		cout << "total: " << c << endl;
	}
}
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信