首页 > 代码库 > HDU 2896 ac自动机裸题
HDU 2896 ac自动机裸题
病毒侵袭
Description
当太阳的光辉逐渐被月亮遮蔽，世界失去了光明，大地迎来最黑暗的时刻。。。。在这样的时刻，人们却异常兴奋――我们能在有生之年看到500年一遇的世界奇观，那是多么幸福的事儿啊~~
但网路上总有那么些网站，开始借着民众的好奇心，打着介绍日食的旗号，大肆传播病毒。小t不幸成为受害者之一。小t如此生气，他决定要把世界上所有带病毒的网站都找出来。当然，谁都知道这是不可能的。小t却执意要完成这不能的任务，他说：“子子孙孙无穷匮也！”（愚公后继有人了）。
万事开头难，小t收集了好多病毒的特征码，又收集了一批诡异网站的源码，他想知道这些网站中哪些是有病毒的，又是带了怎样的病毒呢？顺便还想知道他到底收集了多少带病毒的网站。这时候他却不知道何从下手了。所以想请大家帮帮忙。小t又是个急性子哦，所以解决问题越快越好哦~~
但网路上总有那么些网站，开始借着民众的好奇心，打着介绍日食的旗号，大肆传播病毒。小t不幸成为受害者之一。小t如此生气，他决定要把世界上所有带病毒的网站都找出来。当然，谁都知道这是不可能的。小t却执意要完成这不能的任务，他说：“子子孙孙无穷匮也！”（愚公后继有人了）。
万事开头难，小t收集了好多病毒的特征码，又收集了一批诡异网站的源码，他想知道这些网站中哪些是有病毒的，又是带了怎样的病毒呢？顺便还想知道他到底收集了多少带病毒的网站。这时候他却不知道何从下手了。所以想请大家帮帮忙。小t又是个急性子哦，所以解决问题越快越好哦~~
Input
第一行，一个整数N（1<=N<=500），表示病毒特征码的个数。
接下来N行，每行表示一个病毒特征码，特征码字符串长度在20―200之间。
每个病毒都有一个编号，依此为1―N。
不同编号的病毒特征码不会相同。
在这之后一行，有一个整数M（1<=M<=1000），表示网站数。
接下来M行，每行表示一个网站源码，源码字符串长度在7000―10000之间。
每个网站都有一个编号，依此为1―M。
以上字符串中字符都是ASCII码可见字符（不包括回车）。
接下来N行，每行表示一个病毒特征码，特征码字符串长度在20―200之间。
每个病毒都有一个编号，依此为1―N。
不同编号的病毒特征码不会相同。
在这之后一行，有一个整数M（1<=M<=1000），表示网站数。
接下来M行，每行表示一个网站源码，源码字符串长度在7000―10000之间。
每个网站都有一个编号，依此为1―M。
以上字符串中字符都是ASCII码可见字符（不包括回车）。
Output
依次按如下格式输出按网站编号从小到大输出，带病毒的网站编号和包含病毒编号，每行一个含毒网站信息。
web 网站编号: 病毒编号 病毒编号 …
冒号后有一个空格，病毒编号按从小到大排列，两个病毒编号之间用一个空格隔开，如果一个网站包含病毒，病毒数不会超过3个。
最后一行输出统计信息，如下格式
total: 带病毒网站数
冒号后有一个空格。
web 网站编号: 病毒编号 病毒编号 …
冒号后有一个空格，病毒编号按从小到大排列，两个病毒编号之间用一个空格隔开，如果一个网站包含病毒，病毒数不会超过3个。
最后一行输出统计信息，如下格式
total: 带病毒网站数
冒号后有一个空格。
Sample Input
3aaabbbccc2aaabbbcccbbaacc
Sample Output
web 1: 1 2 3total: 1
稍微修改一下模板，记录模式串到达Tire末尾节点的标号
要选用队列的数据结构，和c++编译。。。否则会MLE
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <queue> 5 #include <cstdlib> 6 using namespace std; 7 const int MAX = 128; 8 struct node { 9 node *fail; 10 node *next[MAX]; 11 int cnt; 12 node() { 13 fail = NULL; 14 cnt = 0; 15 memset(next, 0, sizeof(next)); 16 } 17 }; 18 char keyword[205]; 19 char str[100010]; 20 int head, tail, id; 21 bool vis[505]; 22 void insert(char *str, node *root) { 23 node *p = root; 24 int i = 0, index; 25 while(str[i]) { 26 index = str[i]; 27 if(p->next[index] == NULL) p->next[index] = new node(); 28 p = p->next[index]; 29 i++; 30 } 31 p->cnt = ++id; 32 } 33 void build_ac_automation(node *root) { 34 int i; 35 root->fail = NULL; 36 queue<node*>q; 37 q.push(root); 38 while(!q.empty()) { 39 node *temp = q.front(); 40 q.pop(); 41 node *p = NULL; 42 for(i = 0; i < MAX; i++) { 43 if(temp->next[i] != NULL) { 44 if(temp == root) temp->next[i]->fail = root; 45 else { 46 p = temp->fail; 47 while(p != NULL) { 48 if(p->next[i] != NULL) { 49 temp->next[i]->fail = p->next[i]; 50 break; 51 } 52 p = p->fail; 53 } 54 if(p == NULL) temp->next[i]->fail = root; 55 56 } 57 q.push(temp->next[i]); 58 } 59 } 60 } 61 } 62 int query(node *root) { 63 int i = 0, cnt = 0, index; 64 node *p = root; 65 while(str[i]) { 66 index = str[i]; 67 while(p->next[index] == NULL && p != root) p = p->fail; 68 p = p->next[index]; 69 p = (p == NULL)? root:p; 70 node *temp = p; 71 while(temp != root && temp->cnt != 0 && !vis[temp->cnt]) { 72 vis[temp->cnt] = true; 73 cnt ++; 74 temp = temp->fail; 75 } 76 i++; 77 } 78 return cnt; 79 } 80 int main() { 81 int n, m; 82 while(scanf("%d", &n)!=EOF) { 83 head = tail = id = 0; 84 node * root = new node(); 85 for(int i = 1; i <= n; i++) { 86 scanf("%s", keyword); 87 insert(keyword, root); 88 } 89 build_ac_automation(root); 90 scanf("%d", &m); 91 int res = 0; 92 for(int i = 1; i <= m; i++) { 93 scanf("%s", str); 94 memset(vis,0, sizeof(vis)); 95 int ans = query(root); 96 if(ans > 0) { 97 res++; 98 printf("web %d:", i); 99 for(int j = 1; j < 505; j++) {100 if(vis[j]) printf(" %d", j);101 }102 printf("\n");103 }104 }105 printf("total: %d\n", res);106 }107 //system("pause");108 return 0;109 }
HDU 2896 ac自动机裸题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。