首页 > 代码库 > 【HDOJ】2896 病毒侵袭
【HDOJ】2896 病毒侵袭
AC自动机模板题。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 using namespace std; 6 7 #define TRIEN 128 8 #define MAXN 505 9 10 typedef struct Trie { 11 int in; 12 Trie *fail; 13 Trie *next[TRIEN]; 14 Trie() { 15 in = 0; 16 fail = NULL; 17 memset(next, 0, sizeof(next)); 18 } 19 } Trie; 20 21 Trie *root; 22 char src[205], des[10005]; 23 bool visit[MAXN]; 24 25 void create(char str[], int in) { 26 int i = 0, id; 27 Trie *p = root, *q; 28 29 while (str[i]) { 30 id = str[i]; 31 ++i; 32 if (p->next[id] == NULL) { 33 q = new Trie(); 34 p->next[id] = q; 35 } 36 p = p->next[id]; 37 } 38 p->in = in; 39 } 40 41 void build_fail() { 42 int i; 43 Trie *p, *q; 44 queue<Trie *> que; 45 46 for (i=0; i<TRIEN; ++i) { 47 if (root->next[i]) { 48 root->next[i]->fail = root; 49 que.push(root->next[i]); 50 } 51 } 52 53 while (!que.empty()) { 54 p = que.front(); 55 que.pop(); 56 for (i=0; i<TRIEN; ++i) { 57 if (p->next[i]) { 58 q = p->fail; 59 while (q != NULL) { 60 if (q->next[i]) { 61 p->next[i]->fail = q->next[i]; 62 break; 63 } 64 q = q->fail; 65 } 66 if (q == NULL) 67 p->next[i]->fail = root; 68 que.push(p->next[i]); 69 } 70 } 71 } 72 } 73 74 void search() { 75 int i = 0, id; 76 Trie *p = root, *tmp; 77 78 while (des[i]) { 79 id = des[i]; 80 ++i; 81 while (p->next[id]==NULL && p!=root) 82 p = p->fail; 83 p = p->next[id]; 84 if (p == NULL) 85 p = root; 86 tmp = p; 87 while (tmp != root) { 88 visit[tmp->in] = true; 89 tmp = tmp->fail; 90 } 91 } 92 } 93 94 void del(Trie *t) { 95 if (t == NULL) 96 return ; 97 for (int i=0; i<TRIEN; ++i) 98 del(t->next[i]); 99 delete t;100 }101 102 int main() {103 int n, m, cnt, total;104 int i;105 106 while (scanf("%d",&n) != EOF) {107 root = new Trie();108 for (i=1; i<=n; ++i) {109 scanf("%s", src);110 create(src, i);111 }112 build_fail();113 scanf("%d", &m);114 total = 0;115 for (i=1; i<=m; ++i) {116 scanf("%s", des);117 memset(visit, false, sizeof(visit));118 search();119 cnt = 0;120 for (int j=1; j<=n; ++j) {121 if (visit[j]) {122 if (!cnt)123 printf("web %d:", i);124 ++cnt;125 printf(" %d", j);126 }127 }128 if (cnt) {129 printf("\n");130 ++total;131 }132 }133 printf("total: %d\n", total);134 del(root);135 }136 137 return 0;138 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。