HDU

最近正在学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("******
")
 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("]
");
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
",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("******
")
 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("
");
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("]
");
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
",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("******
")
 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
",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("]
");
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("]
");
 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
", ac.query(buf, tot, n));
135         }
136         printf("
");
137     }
138     return 0;
139 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/qldabiaoge/p/11375776.html