本文共 10432 字，大约阅读时间需要 34 分钟。
最近正在学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 #include2 #include
病毒侵袭 HDU - 2896
给出n个模式串，对m个串进行匹配，输出匹配的模式串的编号，以及总共多少个串可以匹配。
字符总数有128，而且编号要排序。
1 #include2 #include
病毒侵袭持续中 HDU - 3065
这题题意和上一题一样，多了一个输出出现次数。
1 #include2 #include
Detect the Virus ZOJ - 3430
这题本质上还是和上面一个套路只是恶心了很多。
题目是给先你n组经过编码后的病毒串：
编码就是将原串转成二进制后取每6位进行转化成10进制后与上面表格对应的字符串，
末尾不足6位补0，且原串个数为3k+1则在编码后的串里增加'==',
若个数为3k+2则增加'=',给定的模式串也是编码后的串，
所以需要进行反编码然后就是赤裸裸的AC自动机模版了。
注意转化后的字符范围为256（包括转义字符），strlen也无法使用，需要用unsigned char
1 #include2 #include 3 #include 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 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 }
转载于:https://www.cnblogs.com/qldabiaoge/p/11375776.html