hdu 3065 病毒侵袭持续中 (ac自动机)
题目链接
题意：给出n个病毒的模式串，问每个病毒串在文本串中出现了多少次。
思路：ac自动机。模式串只由大写字母组成。文本串是所有可视字符。 如果动态128会MLE.做法是换成静态数组写法，或者对于每次Search的时候，出现非大写字母的字符特判一下。
AC自动机
2016
hdu 2896 病毒侵袭 (ac自动机)
hdu 2896 题目链接
题意：给出n个病毒，然后给出m个网站，然后问每个网站中有哪些病毒，以及有病毒的网站的个数。
需要注意病毒和网站都需要按从小到达排列输出。
思路：ac自动机，需要记录病毒id…然后。。因为病毒的id忘记排序wa了好多发。。智力减2.
ac自动机模板by Lalatina （hdu 2222）
orzorz 日常%学弟 华科的未来orz
代码实现 1#include <cstdio> 2#include <cstring> 3 4using namespace std; 5 6struct tnode { 7 int s; 8 tnode *f, *w, *c[26]; 9} T[5000000], *Q[5000000]; 10int C; 11 12inline tnode *tnew() { 13 memset(T + C, 0, sizeof(tnode)); 14 return T + C++; 15} 16 17inline void AcaInsert(tnode *p, const char *s) { 18 while (*s) { 19 int u = *s - 'a'; 20 if (!p->c[u]) 21 p->c[u] = tnew(); 22 p = p->c[u]; 23 ++s; 24 } 25 ++p->s; 26} 27 28inline void AcaBuild(tnode *p) { 29 p->f = p->w = p; 30 int ql = 0; 31 for (int i = 0; i < 26; ++i) 32 if (p->c[i]) { 33 p->c[i]->f = p->c[i]->w = p; 34 Q[ql++] = p->c[i]; 35 } 36 for (int qf = 0; qf < ql; ++qf) 37 for (int i = 0; i < 26; ++i) 38 if (Q[qf]->c[i]) { 39 tnode *f = Q[qf]->f; 40 while (f != p && !f->c[i]) 41 f = f->f; 42 if (f->c[i]) { 43 Q[qf]->c[i]->f = f->c[i]; 44 Q[qf]->c[i]->w = f->c[i]->s ? f->c[i] : f->c[i]->w; 45 } 46 else 47 Q[qf]->c[i]->f = Q[qf]->c[i]->w = p; 48 Q[ql++] = Q[qf]->c[i]; 49 } 50} 51 52inline int AcaMatch(tnode *root, const char *s) { 53 int x = 0; 54 for (tnode *p = root; *s; ++s) { 55 while (p != root && !p->c[*s - 'a']) 56 p = p->f; 57 if (p->c[*s - 'a']) { 58 p = p->c[*s - 'a']; 59 for (tnode *q = p; q->s != -1; q = q->w) { 60 x += q->s; 61 q->s = -1; 62 } 63 } 64 } 65 return x; 66} 67 68char S[1000001]; 69 70int main() { 71 int tt; 72 scanf("%d", &tt); 73 while (tt--) { 74 C = 0; 75 tnode *root = tnew(); 76 root->s = -1; 77 int N; 78 scanf("%d", &N); 79 while (N--) { 80 scanf("%s", S); 81 AcaInsert(root, S); 82 } 83 AcaBuild(root); 84 scanf("%s", S); 85 printf("%d\n", AcaMatch(root, S)); 86 } 87 return 0; 88}
hdu 2222 Keywords Search (ac自动机模板题（静态数组写法+动态指针写法）)
hdu 2222 题目链接
题意：给出 n 个模式串，一个文本串，问文本串中出现了多少个模式串。
思路：AC 自动机裸题。代码风格来自 bin 神。静态数组的写法。
需要理解在 build fail 的时候，先单独处理 root 的必要性。