Top

AC自动机模板

经常用来解决多模式匹配问题：就是有多个模式串P1,P2,P3…，Pm，求出所有这些模式串在连续文本T1….n中的所有可能出现的位置。

  • 例如：求出模式集合{“nihao”,”hao”,”hs”,”hsr”}在给定文本”sdmfhsgnshejfgnihaofhsrnihao”中所有可能出现的位置
  • 给出L个模式字符串（加总长度为N），以及长度为M大文本，要求从大文本中提取每个模式字符串出现的位置。如果使用KMP算法，时间复杂度将达到O(LM+N)，而使用AC自动机可以在O(N+M)时间复杂度内解决这一问题，当L很大时，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
#include<stdio.h>
#include<bits/stdc++.h>
#define ll long long int
#define max_n 1000050
#define max_tot 500050
#define met(a) memset(a,0,sizeof(a))
#define fup(i,a,n,b) for(int i=a;i<n;i+=b)
#define fow(j,a,n,b) for(int j=a;j>0;j-=b)
#define MOD(x) (x)%mod
using namespace std;
const int maxn = 1e5 + 7;
struct Ac {
	struct state {  //节点状态
		int next[26];
		int fail, cnt;//指针fail 到这个节点有cnt个串结束
	}stable[max_tot];
	int size;  //当前AC自动机节点个数
	queue<int>q;
	void init() {  //初始化
		met(stable);
		size = 1;
		while (!q.empty())q.pop();
	}
	void insert(char *s) {  //将模式串插入trie树
		int now = 0; //代表走到那个节点
		for (int i = 0; s[i]; i++) {
			char ch = s[i]-'a';
			if (!stable[now].next[ch])  //节点不存在该字母边，则新建一个
				stable[now].next[ch] = size++;
			now = stable[now].next[ch];
		}
		stable[now].cnt++;//结束位置++；
	}
	void build() {  //构造失配fail指针，要构造当前节点fail指针需先构造爸爸节点
		for (int i = 0; i < 26; i++)if (stable[0].next[i])q.push(stable[0].next[i]);
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			for (int i = 0; i < 26; i++) {
				if (stable[u].next[i]) {  //如果有i这条边  枚举下他儿子
						int v = stable[u].fail;
						int a = stable[u].next[i];
						while (v) {  //一直按箭头的fail
							if (stable[v].next[i]) {  //如果他某个祖先有i这条边
								stable[a].fail = stable[v].next[i];
								break;
							}
							v = stable[v].fail;
						}
						if (!stable[a].fail)stable[a].fail = stable[0].next[i];
						q.push(stable[u].next[i]);  //节点加进去
				}
			}
		}
	}
	int get(int u) {  //算所有祖先的和
		int res = 0;
		while (u) {
			res = res + stable[u].cnt;
			stable[u].cnt = 0;  //计算后不再计算，如果要计算不清零
			u = stable[u].fail;
		}
		return res;
	}
	int match(char *s) {   //匹配
		int res = 0, now = 0;
		for (int i = 0; s[i]; i++) {
			char ch = s[i]-'a';
			if (stable[now].next[ch])  //如果当前状态太能找到后继节点，则走他
				now = stable[now].next[ch];
			else {  //否则只能跳爸爸
				int p = stable[now].fail;
				while (p && stable[p].next[ch] == 0)p = stable[p].fail; //始终没找到，只能指根节点  //找到就跳对应地方
				now = stable[p].next[ch];
			}
			if (stable[now].cnt)res = res + get(now);//
		}
		return res;
	}
}Ac;
char s[max_n];
int main(int argc, char *argv[]) {
#ifdef LOCAL
	freopen("C:/input.txt", "r", stdin);
#endif
}

应用：查找母串中各单词出现次数–对应题目P3796

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
#include<stdio.h>
#include<bits/stdc++.h>
#define ll long long int
#define max_n 1000050
#define max_tot 500050
#define met(a) memset(a,0,sizeof(a))
#define fup(i,a,n,b) for(int i=a;i<n;i+=b)
#define fow(j,a,n,b) for(int j=a;j>0;j-=b)
#define MOD(x) (x)%mod
using namespace std;
const int maxn = 1e5 + 7;
struct aa {
	int i;
	int cnt;
}ans[180];
int cmp(aa a, aa b) {
	if (a.cnt == b.cnt)return a.i < b.i;
	else return a.cnt > b.cnt;
}
struct Ac {
	struct state {  //节点状态
		int next[26];
		int fail, cnt;//指针fail 到这个节点有cnt个串结束
	}stable[max_tot];
	int size;  //当前AC自动机节点个数
	queue<int>q;
	void init() {  //初始化
		met(stable);
		size = 1;
		while (!q.empty())q.pop();
		for (int i = 0; i <= 150; i++) {
			ans[i].i = i;
			ans[i].cnt = 0;
		}
	}
	void insert(char *s,int n) {  //将模式串插入trie树
		int now = 0; //代表走到那个节点
		for (int i = 0; s[i]; i++) {
			char ch = s[i]-'a';
			if (!stable[now].next[ch])  //节点不存在该字母边，则新建一个
				stable[now].next[ch] = size++;
			now = stable[now].next[ch];
		}
		stable[now].cnt=n;//结束位置++；
	}
	void build() {  //构造失配fail指针，要构造当前节点fail指针需先构造爸爸节点
		for (int i = 0; i < 26; i++)if (stable[0].next[i])q.push(stable[0].next[i]);
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			for (int i = 0; i < 26; i++) {
				if (stable[u].next[i]) {  //如果有i这条边  枚举下他儿子
						int v = stable[u].fail;
						int a = stable[u].next[i];
						while (v) {  //一直按箭头的fail
							if (stable[v].next[i]) {  //如果他某个祖先有i这条边
								stable[a].fail = stable[v].next[i];
								break;
							}
							v = stable[v].fail;
						}
						if (!stable[a].fail)stable[a].fail = stable[0].next[i];
						q.push(stable[u].next[i]);  //节点加进去
				}
			}
		}
	}
	void get(int u) {  //算所有祖先的和
		int res = 0;
		u = stable[u].fail;
		while (u) {
			if(stable[u].cnt)ans[stable[u].cnt].cnt++;  //找个数
			u = stable[u].fail;
		}
		return;
	}
	int match(char *s) {   //匹配
		int res = 0, now = 0;
		for (int i = 0; s[i]; i++) {
			char ch = s[i]-'a';
			if (stable[now].next[ch])  //如果当前状态太能找到后继节点，则走他
				now = stable[now].next[ch];
			else {  //否则只能跳爸爸
				int p = stable[now].fail;
				while (p && stable[p].next[ch] == 0)p = stable[p].fail; //始终没找到，只能指根节点  //找到就跳对应地方
				now = stable[p].next[ch];
			}
			if (stable[now].cnt) { 
				ans[stable[now].cnt].cnt++; 
			}
			get(now);
			
		}
		return res;
	}
}Ac;
char s[max_n];
char s1[200][80];
int main(int argc, char *argv[]) {
	/*ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);*/
	int t, n;
	while (scanf("%d", &n)&&n!=0) {
		Ac.init();
		for (int i = 1; i <= n; i++) {
			scanf("%s", s1[i]);
			Ac.insert(s1[i], i);
		}
		Ac.build();

		scanf("%s", s);
		Ac.match(s);

		sort(ans, ans + n+1, cmp);
		printf("%d\n", ans[0].cnt);
		printf("%s\n", s1[ans[0].i]);
		for (int i = 1; i < n; i++) {
			if (ans[i].cnt == ans[0].cnt)printf("%s\n", s1[ans[i].i]);
			else break;
		}
	}
	return 0;
}


未经允许不得转载： Anoyer's Blog » AC自动机模板
 ACM模板
 上一篇