Dyd's Blog

He who has a strong enough why can bear almost any how.

AC自动机

Posted on Edited on In
Symbols count in article: 6.3k Reading time ≈ 6 mins.

然而AC自动机并不能自动帮你AC

钳制芝士

  • KMP
    对字符串 $A$ 进行自我匹配，求出数组 $ne$ 使 $ne[i]$ 表示“ $A$ 中以 $i$ 结尾的非前缀子串与 $A$ 的前缀子串能匹配的最长长度”，即： $ne[i]=max{j}$ ，其中 $j<i$ 并且 $\forall k \in [i-j+1,i],A[k]=A[k+j-i]$ （ $A[k+j-i]$ 即是 $A[1 \sim j]$ ） ，如图：KMP例子
    同理我们对字符串 $A$ 与 $B$ 进行匹配，求出数组 $f$ ，使 $f[i]$ 表示“ $B$ 中以 $i$ 结尾的子串与 $A$ 的前缀子串能匹配的最长长度”,即： $f[i]=max{j}$ ，其中 $j \le i$ 并且 $\forall k \in [i-j+1,i],B[k]=A[k+j-i]$
    代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//求ne数组
ne[1]=0;
for(int i=2,j=0;i<=n;++i){		//"非前缀子串",故i从2开始 
	while(j>0&&a[i]!=a[j+1]) j=ne[j];
	if(a[i]==a[j+1]) ++j;
	ne[i]=j;
}
//求f数组
for(int i=1,j=0;i<=m;++i){
	while(j>0&&(j==n||b[i]!=a[j+1])) j=ne[j];
	if(b[i]==a[j+1]) ++j;
	f[i]=j;
	if(f[i]==n){
		//此时就是A在B中的一次出现 
	}
}
  • Trie（字典树）
    用于统计，排序和保存大量的字符串（但不仅限于字符串），优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。
    Trie
    代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int trie[N][26],tot=1;	//设字符串由小写字母构成
bool end[N];
//插入一个字符串
void insert(char* s){
	int l=strlen(s),p=1;
	for(int k=0;k<l;++k){
		int ch=s[k]-'a';
		if(trie[p][ch]==0) trie[p][ch]=++tot;
		p=trie[p][ch];
	}
	end[p]=true;
} 
// 搜索一个字符串
bool search(char* s){
	int l=strlen(s),p=1;
	for(int k=0;k<l;++k){
		p=trie[p][s[k]-'a'];
		if(p==0) return false;
	}
return end[p];
}

AC自动机

大家都知道KMP算法是求单字符串对单字符串的匹配使用的，那么，多个字符串在一个字符串上的匹配怎么办？ 如：
求 abab 在 abababbabbaabbabbab 中出现了几次。
很明显，求出abab的 $ne$ 数组，然后进行KMP的匹配即可出解。
辣么——求 aba 、 aca 、 bab 、 sab 、 sba 在字符串 asabbasbaabbabbacaacbscbs 中总共出现了几次。此时如果再对于每一个需要匹配的串求一次 $ne$ 数组，时间复杂度过大了……
辣么，AC自动机是如何解决此问题的呢？

开始前，先看看定义：

1
2
3
4
5
struct Trie{	//字典树 
	int fail;	//失配指针 
	int vis[26];	//子节点位置 
	int end;	//标记结尾
}ac[N];

然后开始吧！
首先，将所有的需要匹配的字符串构造成一棵Tire树，如图（灰色节点表示一个单词的结尾）：待匹配串
然后，类似于KMP建立失配指针（即 $ne$ 数组），其定义为：当前节点所代表的串中，最长的、能与后缀匹配的，在 Trie 中出现过的前缀所代表的节点。
类似的，可以通过跳转来省略重复的检查。
如图是已建立好的：失配
每次沿着Trie树匹配，匹配到当前位置没有匹配上时，直接跳转到失配指针所指向的位置继续进行匹配。
所以，这个Trie树的失配指针要怎么求？
我们发现Trie树的失配指针是指向：沿着其父节点的失配指针，一直向上，直到找到拥有当前这个字母为子节点的节点，它的那个子节点就是目标。
如上图中 she 中的 e ，它的父节点是 h （ s 下面那个），而 h 的失配指针指向另一个 h （根下面那个），且这个 h 的子节点中有一个 e ，就将 she 中的 e 指向这个 e 。
需要注意的是，若找不到符合要求的节点，就将失配指针指向根，不难发现，第二层的所有节点的失配指针，都要直接指向Trie树的根节点。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//构造fail指针 
void Get_fail(){
	queue<int>q;
	for(int i=0;i<26;++i)	//第二层的fail指针预处理 
		if(ac[0].vis[i]!=0){
			ac[ac[0].vis[i]].fail=0;	//指向根节点 
			q.push(ac[0].vis[i]);	//入队 
		}
	while(!q.empty()){	//BFS求fail指针 
		int u=q.front();q.pop();
		for(int i=0;i<26;++i)	//枚举子节点 
			if(ac[u].vis[i]!=0){	//该节点存在 
				ac[ac[u].vis[i]].fail=ac[ac[u].fail].vis[i];	//子节点的fail指针 指向当前节点的
																//fail指针 所指向的节点 的相同子节点 
				q.push(ac[u].vis[i]);	//入队 
			}
			else	//不存在这个子节点 
				ac[u].vis[i]=ac[ac[u].fail].vis[i];	 //当前节点的这个子节点指向当
                     								 //前节点fail指针的这个子节点
	} 
	return ;
}

最后，我们直接匹配即可了！先让指针指向根节点
依次读入单词，检查是否存在这个子节点，然后指针跳转到子节点，如果不存在，直接跳转到失配指针即可。

1
2
3
4
5
6
7
8
9
10
11
//AC自动机匹配
void Ac_query(string s){
	int l=s.length();
	int now=0;
	for(int i=0;i<l;++i){
		now=ac[now].vis[s[i]-'a'];	//向下一层
		for(int t=now;t;t=ac[t].fail)	//循环求解 
			ans[ac[t].end].num++;
	}
	return ;
}

最后给出总的代码（尝试了一下标准码风）：

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
//P376
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
struct Trie
{
	int fail;
	int vis[26];
	int end;
} ac[N];
int cnt = 0;
struct Result
{
	int num;
	int pos;
	bool operator<(const Result &y)
	{
		return num != y.num ? num > y.num : pos < y.pos;
	}
	void inint(int _num, int _pos)
	{
		num = _num;
		pos = _pos;
		return;
	}
} ans[N];
string s[N];
void clean(int x)
{
	memset(ac[x].vis, 0, sizeof ac[x].vis);
	ac[x].fail = 0;
	ac[x].end = 0;
	return;
}
void build_Trie(string s, int Num)
{
	int l = s.length();
	int now = 0;
	for (int i = 0; i < l; ++i)
	{
		if (ac[now].vis[s[i] - 'a'] == 0)
		{
			ac[now].vis[s[i] - 'a'] = ++cnt;
			clean(cnt);
		}
		now = ac[now].vis[s[i] - 'a'];
	}
	ac[now].end = Num;
	return;
}
void get_fail()
{
	queue<int> q;
	for (int i = 0; i < 26; ++i)
		if (ac[0].vis[i] != 0)
		{
			ac[ac[0].vis[i]].fail = 0;
			q.push(ac[0].vis[i]);
		}
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		for (int i = 0; i < 26; ++i)
			if (ac[u].vis[i] != 0)
			{
				ac[ac[u].vis[i]].fail = ac[ac[u].fail].vis[i];
				q.push(ac[u].vis[i]);
			}
			else
				ac[u].vis[i] = ac[ac[u].fail].vis[i];
	}
	return;
}
void AC_query(string s)
{
	int l = s.length();
	int now = 0;
	for (int i = 0; i < l; ++i)
	{
		now = ac[now].vis[s[i] - 'a'];
		for (int t = now; t; t = ac[t].fail)
			ans[ac[t].end].num++;
	}
	return;
}
int main()
{
	int n;
	while (1)
	{
		cin >> n;
		if (n == 0)
			break;
		cnt = 0;
		clean(0);
		for (int i = 1; i <= n; ++i)
		{
			cin >> s[i];
			ans[i].inint(0, i);
			build_Trie(s[i], i);
		}
		ac[0].fail = 0;
		get_fail();
		cin >> s[0];
		AC_query(s[0]);
		sort(ans + 1, ans + 1 + n);
		cout << ans[1].num << endl;
		cout << s[ans[1].pos] << endl;
		for (int i = 2; i <= n; ++i)
			if (ans[i].num == ans[i - 1].num)
				cout << s[ans[i].pos] << endl;
			else
				break;
	}
	return 0;
}

补充，可以把搜索过程改为拓扑序，可以过加强版

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
//P5357
#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
struct Trie
{
	int fail;
	int vis[26];
	int end;
	int as;
} ac[N];
int cnt = 0;
int re[N], in[N], ans[N];
string s[N];
queue<int> q;
void build_Trie(string s, int Num)
{
	int l = s.length();
	int now = 0;
	for (int i = 0; i < l; ++i)
	{
		if (!ac[now].vis[s[i] - 'a'])
			ac[now].vis[s[i] - 'a'] = ++cnt;
		now = ac[now].vis[s[i] - 'a'];
	}
	if (!ac[now].end)
		ac[now].end = Num;
	re[Num] = ac[now].end;
	return;
}
void get_fail()
{

	for (int i = 0; i < 26; ++i)
		if (ac[0].vis[i] != 0)
		{
			ac[ac[0].vis[i]].fail = 0;
			q.push(ac[0].vis[i]);
		}
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		for (int i = 0; i < 26; ++i)
		{
			int v = ac[u].vis[i];
			if (v)
			{
				ac[v].fail = ac[ac[u].fail].vis[i];
				in[ac[v].fail]++;
				q.push(v);
			}
			else
				ac[u].vis[i] = ac[ac[u].fail].vis[i];
		}
	}
	return;
}
void AC_query(string s)
{
	int l = s.length();
	int now = 0;
	for (int i = 0; i < l; ++i)
	{
		now = ac[now].vis[s[i] - 'a'];
		ac[now].as++;
	}
	return;
}
void topu()
{
	for (int i = 1; i <= cnt; ++i)
		if (!in[i])
			q.push(i);
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		ans[ac[u].end] = ac[u].as;
		int v = ac[u].fail;
		in[v]--;
		ac[v].as += ac[u].as;
		if (!in[v])
			q.push(v);
	}
	return;
}
int main()
{
	int n;
	cin >> n;
	cnt = 0;
	for (int i = 1; i <= n; ++i)
	{
		cin >> s[i];
		build_Trie(s[i], i);
	}
	ac[0].fail = 0;
	get_fail();
	cin >> s[0];
	AC_query(s[0]);
	topu();
	for (int i = 1; i <= n; ++i)
		cout << ans[re[i]] << endl;
	return 0;
}