最近正在学AC自动机，按照惯例需要刷一套kuangbin的AC自动机专题巩固
在网上看过很多模板，感觉kuangbin大神的模板最为简洁，于是就选择了用kuangbin大神的模板。
AC自动机其实就是字典树和KMP的结合，然后去思考一下KMP的原理，然后就是在字典树上实现KMP
这里最重要的思想可能就是fail的思想，就像KMP一样，匹配失败后，有一个next的数组去回溯(最长公共前缀后缀)
如何理解了KMP的话，感觉这个不会很难理解，字典树是一个非常简单的东西就不用讲了吧。
HDU - 2222,HDU - 2896,HDU - 3065,ZOJ - 3430
这是我总结出来的AC自动机解决的第一类问题，求文本串和模式串的关系(模式串出现几次之类的问题)
我把这几题放一起写了算了，因为套路一样随便改一下就好了
Keywords Search HDU - 2222
询问有多少个模式串出现在了文本串里面。
将模式串插入Trie树中，然后直接查询就好了。
1 #include <set>
2 #include <map>
3 #include <stack>
4 #include <queue>
5 #include <cmath>
6 #include <cstdio>
7 #include <string>
8 #include <vector>
9 #include <time.h>
10 #include <cstring>
11 #include <iostream>
12 #include <algorithm>
13 #include <unordered_map>
14
15 #define pi acos(-1.0)
16 #define eps 1e-9
17 #define fi first
18 #define se second
19 #define rtl rt<<1
20 #define rtr rt<<1|1
21 #define bug printf("******\n")
22 #define mem(a, b) memset(a,b,sizeof(a))
23 #define name2str(x) #x
24 #define fuck(x) cout<<#x" = "<<x<<endl
25 #define sf(n) scanf("%d", &n)
26 #define sff(a, b) scanf("%d %d", &a, &b)
27 #define sfff(a, b, c) scanf("%d %d %d", &a, &b, &c)
28 #define sffff(a, b, c, d) scanf("%d %d %d %d", &a, &b, &c, &d)
29 #define pf printf
30 #define FIN freopen("data.txt","r",stdin)
31 #define gcd(a, b) __gcd(a,b)
32 #define lowbit(x) x&-x
33 #define IO iOS::sync_with_stdio(false)
34
35
36 using namespace std;
37 typedef long long LL;
38 typedef unsigned long long ULL;
39 const int maxn = 1e6 + 7;
40 const int maxm = 8e6 + 10;
41 const int INF = 0x3f3f3f3f;
42 const int mod = 1e9 + 7;
43
44 struct Aho_Corasick {
45 int next[500010][26], fail[500010], End[500010];
46 int root, cnt;
47
48 int newnode() {
49 for (int i = 0; i < 26; i++) next[cnt][i] = -1;
50 End[cnt++] = 0;
51 return cnt - 1;
52 }
53
54 void init() {
55 cnt = 0;
56 root = newnode();
57 }
58
59 void insert(char buf[]) {
60 int len = strlen(buf);
61 int now = root;
62 for (int i = 0; i < len; i++) {
63 if (next[now][buf[i] - 'a'] == -1) next[now][buf[i] - 'a'] = newnode();
64 now = next[now][buf[i] - 'a'];
65 }
66 End[now]++;
67 }
68
69 void build() {
70 queue<int> Q;
71 fail[root] = root;
72 for (int i = 0; i < 26; i++)
73 if (next[root][i] == -1) next[root][i] = root;
74 else {
75 fail[next[root][i]] = root;
76 Q.push(next[root][i]);
77 }
78 while (!Q.empty()) {
79 int now = Q.front();
80 Q.pop();
81 for (int i = 0; i < 26; i++)
82 if (next[now][i] == -1) next[now][i] = next[fail[now]][i];
83 else {
84 fail[next[now][i]] = next[fail[now]][i];
85 Q.push(next[now][i]);
86 }
87 }
88 }
89
90 int query(char buf[]) {
91 int len = strlen(buf);
92 int now = root;
93 int res = 0;
94 for (int i = 0; i < len; i++) {
95 now = next[now][buf[i] - 'a'];
96 int temp = now;
97 while (temp != root) {
98 res += End[temp];
99 End[temp] = 0;
100 temp = fail[temp];
101 }
102 }
103 return res;
104 }
105
106 void debug() {
107 for (int i = 0; i < cnt; i++) {
108 printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], End[i]);
109 for (int j = 0; j < 26; j++) printf("%2d", next[i][j]);
110 printf("]\n");
111 }
112 }
113 }ac;
114
115 char buf[1000010];
116 int T,n;
117 int main() {
118 sf(T);
119 while(T--){
120 sf(n);
121 ac.init();
122 for (int i = 0; i < n; ++i) {
123 scanf("%s",buf);
124 ac.insert(buf);
125 }
126 scanf("%s",buf);
127 ac.build();
128 printf("%d\n",ac.query(buf));
129 }
130 return 0;
131 }
View Code
病毒侵袭 HDU - 2896
给出n个模式串，对m个串进行匹配，输出匹配的模式串的编号，以及总共多少个串可以匹配。
字符总数有128，而且编号要排序。
1 #include <set>
2 #include <map>
3 #include <stack>
4 #include <queue>
5 #include <cmath>
6 #include <cstdio>
7 #include <string>
8 #include <vector>
9 #include <time.h>
10 #include <cstring>
11 #include <iostream>
12 #include <algorithm>
13 #include <unordered_map>
14
15 #define pi acos(-1.0)
16 #define eps 1e-9
17 #define fi first
18 #define se second
19 #define rtl rt<<1
20 #define rtr rt<<1|1
21 #define bug printf("******\n")
22 #define mem(a, b) memset(a,b,sizeof(a))
23 #define name2str(x) #x
24 #define fuck(x) cout<<#x" = "<<x<<endl
25 #define sf(n) scanf("%d", &n)
26 #define sff(a, b) scanf("%d %d", &a, &b)
27 #define sfff(a, b, c) scanf("%d %d %d", &a, &b, &c)
28 #define sffff(a, b, c, d) scanf("%d %d %d %d", &a, &b, &c, &d)
29 #define pf printf
30 #define FIN freopen("../date.txt","r",stdin)
31 #define gcd(a, b) __gcd(a,b)
32 #define lowbit(x) x&-x
33 #define IO iOS::sync_with_stdio(false)
34
35
36 using namespace std;
37 typedef long long LL;
38 typedef unsigned long long ULL;
39 const int maxn = 1e6 + 7;
40 const int maxm = 8e6 + 10;
41 const int INF = 0x3f3f3f3f;
42 const int mod = 1e9 + 7;
43
44 struct Aho_Corasick {
45 int next[100010][128], fail[100010], End[100010],vis[100010];
46 int root, cnt;
47 vector<int>ans;
48 int newnode() {
49 for (int i = 0; i < 128; i++) next[cnt][i] = -1;
50 End[cnt++] = 0;
51 return cnt - 1;
52 }
53
54 void init() {
55 cnt = 0;
56 root = newnode();
57 }
58
59 void insert(char buf[],int id) {
60 int len = strlen(buf);
61 int now = root;
62 for (int i = 0; i < len; i++) {
63 if (next[now][buf[i]] == -1) next[now][buf[i]] = newnode();
64 now = next[now][buf[i]];
65 }
66 End[now]++;
67 vis[now]=id;
68 }
69
70 void build() {
71 queue<int> Q;
72 fail[root] = root;
73 for (int i = 0; i < 128; i++)
74 if (next[root][i] == -1) next[root][i] = root;
75 else {
76 fail[next[root][i]] = root;
77 Q.push(next[root][i]);
78 }
79 while (!Q.empty()) {
80 int now = Q.front();
81 Q.pop();
82 for (int i = 0; i < 128; i++)
83 if (next[now][i] == -1) next[now][i] = next[fail[now]][i];
84 else {
85 fail[next[now][i]] = next[fail[now]][i];
86 Q.push(next[now][i]);
87 }
88 }
89 }
90
91 int query(char buf[]) {
92 int len = strlen(buf);
93 int now = root;
94 int res = 0;
95 for (int i = 0; i < len; i++) {
96 now = next[now][buf[i]];
97 int temp = now;
98 while (temp != root) {
99 res += End[temp];
100 if (vis[temp]) ans.push_back(vis[temp]);
101 // End[temp] = 0;
102 temp = fail[temp];
103 }
104 }
105 return res;
106 }
107 void pf_ans(){
108 sort(ans.begin(),ans.end());
109 for (int i=0 ;i<ans.size() ;i++) printf(" %d",ans[i]);
110 printf("\n");
111 ans.clear();
112 }
113 void debug() {
114 for (int i = 0; i < cnt; i++) {
115 printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], End[i]);
116 for (int j = 0; j < 26; j++) printf("%2d", next[i][j]);
117 printf("]\n");
118 }
119 }
120 }ac;
121
122 char buf[1000010];
123 int n,m;
124 int main() {
125 // FIN;
126 while(~sf(n)){
127 ac.init();
128 for (int i = 1; i <= n; ++i) {
129 scanf("%s",buf);
130 ac.insert(buf,i);
131 }
132 ac.build();
133 sf(m);
134 int tot=0;
135 for (int i = 1; i <= m; ++i) {
136 scanf("%s",buf);
137 //fuck(i);
138 if (ac.query(buf)) {
139 tot++;
140 printf("web %d:",i);
141 ac.pf_ans();
142 }
143 }
144 printf("total: %d\n",tot);
145 }
146 return 0;
147 }
View Code
病毒侵袭持续中 HDU - 3065
这题题意和上一题一样，多了一个输出出现次数。
1 #include <set>
2 #include <map>
3 #include <stack>
4 #include <queue>
5 #include <cmath>
6 #include <cstdio>
7 #include <string>
8 #include <vector>
9 #include <time.h>
10 #include <cstring>
11 #include <iostream>
12 #include <algorithm>
13 #include <unordered_map>
14
15 #define pi acos(-1.0)
16 #define eps 1e-9
17 #define fi first
18 #define se second
19 #define rtl rt<<1
20 #define rtr rt<<1|1
21 #define bug printf("******\n")
22 #define mem(a, b) memset(a,b,sizeof(a))
23 #define name2str(x) #x
24 #define fuck(x) cout<<#x" = "<<x<<endl
25 #define sf(n) scanf("%d", &n)
26 #define sff(a, b) scanf("%d %d", &a, &b)
27 #define sfff(a, b, c) scanf("%d %d %d", &a, &b, &c)
28 #define sffff(a, b, c, d) scanf("%d %d %d %d", &a, &b, &c, &d)
29 #define pf printf
30 #define FIN freopen("../date.txt","r",stdin)
31 #define gcd(a, b) __gcd(a,b)
32 #define lowbit(x) x&-x
33 #define IO iOS::sync_with_stdio(false)
34
35
36 using namespace std;
37 typedef long long LL;
38 typedef unsigned long long ULL;
39 const int maxn = 1e6 + 7;
40 const int maxm = 8e6 + 10;
41 const int INF = 0x3f3f3f3f;
42 const int mod = 1e9 + 7;
43
44 char str[1010][100];
45 char buf[2000010];
46 int n, m;
47 struct Aho_Corasick {
48 int next[1010*50][128], fail[1010*50], End[1010*50], num[1010];
49 int root, cnt;
50
51 int newnode() {
52 for (int i = 0; i < 128; i++) next[cnt][i] = -1;
53 End[cnt++] = 0;
54 return cnt - 1;
55 }
56
57 void init() {
58 cnt = 0;
59 root = newnode();
60 }
61
62 void insert(char buf[], int id) {
63 int len = strlen(buf);
64 int now = root;
65 for (int i = 0; i < len; i++) {
66 if (next[now][buf[i]] == -1) next[now][buf[i]] = newnode();
67 now = next[now][buf[i]];
68 }
69 End[now] = id;
70 }
71
72 void build() {
73 queue<int> Q;
74 fail[root] = root;
75 for (int i = 0; i < 128; i++)
76 if (next[root][i] == -1) next[root][i] = root;
77 else {
78 fail[next[root][i]] = root;
79 Q.push(next[root][i]);
80 }
81 while (!Q.empty()) {
82 int now = Q.front();
83 Q.pop();
84 for (int i = 0; i < 128; i++)
85 if (next[now][i] == -1) next[now][i] = next[fail[now]][i];
86 else {
87 fail[next[now][i]] = next[fail[now]][i];
88 Q.push(next[now][i]);
89 }
90 }
91 }
92
93 void query(char buf[]) {
94 for(int i = 1;i <= n;i++) num[i] = 0;
95 int len = strlen(buf);
96 int now = root;
97 for (int i = 0; i < len; i++) {
98 now = next[now][buf[i]];
99 int temp = now;
100 while (temp != root) {
101 if (End[temp]) num[End[temp]]++;
102 // End[temp] = 0;
103 temp = fail[temp];
104 }
105 }
106 for (int i=1 ;i<=n ;i++)
107 if (num[i]) printf("%s: %d\n",str[i],num[i]);
108 }
109
110 void debug() {
111 for (int i = 0; i < cnt; i++) {
112 printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], End[i]);
113 for (int j = 0; j < 26; j++) printf("%2d", next[i][j]);
114 printf("]\n");
115 }
116 }
117 } ac;
118
119
120
121 int main() {
122 //FIN;
123 while (~sf(n)) {
124 ac.init();
125 for (int i = 1; i <= n; ++i) {
126 scanf("%s", str[i]);
127 ac.insert(str[i], i);
128 }
129 ac.build();
130 scanf("%s", buf);
131 ac.query(buf);
132 }
133 return 0;
134 }
View Code
Detect the Virus ZOJ - 3430
这题本质上还是和上面一个套路只是恶心了很多。
题目是给先你n组经过编码后的病毒串：
编码就是将原串转成二进制后取每6位进行转化成10进制后与上面表格对应的字符串，
末尾不足6位补0，且原串个数为3k+1则在编码后的串里增加'==',
若个数为3k+2则增加'=',给定的模式串也是编码后的串，
所以需要进行反编码然后就是赤裸裸的AC自动机模版了。
注意转化后的字符范围为256（包括转义字符），strlen也无法使用，需要用unsigned char
1 #include <cstdio>
2 #include <cstring>
3 #include <queue>
4
5
6 #define sf(n) scanf("%d", &n)
7 #define sff(a, b) scanf("%d %d", &a, &b)
8
9
10 using namespace std;
11 typedef long long LL;
12 typedef unsigned long long ULL;
13 const int maxn = 1e6 + 7;
14 const int maxm = 8e6 + 10;
15 const int INF = 0x3f3f3f3f;
16 const int mod = 1e9 + 7;
17
18 unsigned char buf[2050];
19 char str[4000];
20 unsigned char s[4000];
21 int n, m, tot;
22
23 struct Aho_Corasick {
24 int next[1010 * 50][256], fail[1010 * 50], End[1010 * 50], vis[4005];
25 int root, cnt;
26
27 int newnode() {
28 for (int i = 0; i < 256; i++) next[cnt][i] = -1;
29 End[cnt++] = 0;
30 return cnt - 1;
31 }
32
33 void init() {
34 cnt = 0;
35 root = newnode();
36 }
37
38 void insert(unsigned char buf[], int len, int id) {
39 int now = root;
40 for (int i = 0; i < len; i++) {
41 if (next[now][buf[i]] == -1) next[now][buf[i]] = newnode();
42 now = next[now][buf[i]];
43 }
44 End[now] = id;
45 }
46
47 void build() {
48 queue<int> Q;
49 fail[root] = root;
50 for (int i = 0; i < 256; i++)
51 if (next[root][i] == -1) next[root][i] = root;
52 else {
53 fail[next[root][i]] = root;
54 Q.push(next[root][i]);
55 }
56 while (!Q.empty()) {
57 int now = Q.front();
58 Q.pop();
59 for (int i = 0; i < 256; i++)
60 if (next[now][i] == -1) next[now][i] = next[fail[now]][i];
61 else {
62 fail[next[now][i]] = next[fail[now]][i];
63 Q.push(next[now][i]);
64 }
65 }
66 }
67
68 int query(unsigned char buf[], int len, int n) {
69 memset(vis, false, sizeof(vis));
70 int now = root;
71 for (int i = 0; i < len; i++) {
72 now = next[now][buf[i]];
73 int temp = now;
74 while (temp != root) {
75 if (End[temp] != -1)
76 vis[End[temp]] = true;
77 temp = fail[temp];
78 }
79 }
80 int res = 0;
81 for (int i = 1; i <= n; i++) if (vis[i]) res++;
82 return res;
83 }
84
85 void debug() {
86 for (int i = 0; i < cnt; i++) {
87 printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], End[i]);
88 for (int j = 0; j < 26; j++) printf("%2d", next[i][j]);
89 printf("]\n");
90 }
91 }
92 } ac;
93
94
95 unsigned char Get(char ch) {
96 if (ch >= 'A' && ch <= 'Z')return ch - 'A';
97 if (ch >= 'a' && ch <= 'z')return ch - 'a' + 26;
98 if (ch >= '0' && ch <= '9')return ch - '0' + 52;
99 if (ch == '+')return 62;
100 else return 63;
101 }
102
103 void change(unsigned char str[], int len) {
104 int t = 0;
105 for (int i = 0; i < len; i += 4) {
106 buf[t++] = ((str[i] << 2) | (str[i + 1] >> 4));
107 if (i + 2 < len)
108 buf[t++] = ((str[i + 1] << 4) | (str[i + 2] >> 2));
109 if (i + 3 < len)
110 buf[t++] = ((str[i + 2] << 6) | str[i + 3]);
111 }
112 tot = t;
113 }
114
115 int main() {
116 while (~sf(n)) {
117 ac.init();
118 for (int i = 1; i <= n; ++i) {
119 scanf("%s", str);
120 int len = strlen(str);
121 while (str[len - 1] == '=')len--;
122 for (int j = 0; j < len; j++) s[j] = Get(str[j]);
123 change(s, len);
124 ac.insert(buf, tot, i);
125 }
126 ac.build();
127 sf(m);
128 for (int i = 1; i <= m; i++) {
129 scanf("%s", str);
130 int len = strlen(str);
131 while (str[len - 1] == '=') len--;
132 for (int j = 0; j < len; j++) s[j] = Get(str[j]);
133 change(s, len);
134 printf("%d\n", ac.query(buf, tot, n));
135 }
136 printf("\n");
137 }
138 return 0;
139 }
View Code