首页 > 代码库 > HDU 2896 AC自动机 + 细心
HDU 2896 AC自动机 + 细心
病毒侵袭
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 10478 Accepted Submission(s): 2724
Problem 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
3
aaa
bbb
ccc
2
aaabbbccc
bbaacc
Sample Output
web 1: 1 2 3
total: 1
题目很简单,就是模板题,每个病毒特征码插入字典树的时候顺便插入它的编号,在本题中我用vector存储每个网站所带的病毒编号,枚举每个网站,看是不是空,不是空输出即可。
这道题需要细心,Input最后一句 “以上字符串中字符都是ASCII码可见字符(不包括回车)。” 意味着病毒特征码不一定只由字母构成,可以由任何ASCII码可见字符构成。。。真坑爹,每次提交都显示Runtime Error(ACCESS_VIOLATION) 。。。
一直以为我设置的存储空间不够。。。RE了半个小时才发现。。。
代码:
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <queue> 6 #include <vector> 7 using namespace std; 8 9 char a[205]; 10 char str[10005]; 11 int visited[505]; 12 vector<int>ve[1005]; 13 14 struct node{ 15 int flag; 16 int id; 17 struct node *next[130], *fail; 18 node(){ 19 flag=0; 20 id=0; 21 memset(next,0,sizeof(next)); 22 } 23 }; 24 25 26 void insert(node *root,char *s,int id){ //插入 27 int i=0; 28 node *p=root; 29 while(s[i]){ 30 if(!p->next[(int)s[i]]){ 31 p->next[(int)s[i]]=new node; 32 p=p->next[(int)s[i]]; 33 } 34 else p=p->next[(int)s[i]]; 35 i++; 36 } 37 p->id=id; 38 p->flag=1; 39 } 40 41 void get_fail(node *root){ //设置tree 的fail指针 42 node *p, *tmp; 43 queue<node*>Q; 44 Q.push(root); 45 int i; 46 root->fail=NULL; 47 while(!Q.empty()){ 48 p=Q.front(); 49 Q.pop(); 50 for(i=0;i<130;i++){ 51 if(p->next[i]){ 52 if(p==root) p->next[i]->fail=root; 53 else{ 54 tmp=p->fail; 55 while(tmp){ 56 if(tmp->next[i]){ 57 p->next[i]->fail=tmp->next[i]; 58 break; 59 } 60 tmp=tmp->fail; 61 } 62 if(tmp==NULL) p->next[i]->fail=root; 63 } 64 Q.push(p->next[i]); 65 } 66 } 67 } 68 } 69 70 71 void solve(node *root,char *s,int k){ //解决问题 72 int j=0, i; 73 node *p=root, *tmp; 74 while(s[j]){ 75 i=s[j]; 76 while(!p->next[i]&&p!=root) p=p->fail; 77 p=p->next[i]; 78 if(p==NULL) p=root; 79 tmp=p; 80 while(tmp->flag&&tmp!=root&&!visited[tmp->id]){ 81 visited[tmp->id]=1; 82 ve[k].push_back(tmp->id); 83 tmp=tmp->fail; 84 } 85 j++; 86 } 87 88 } 89 main() 90 { 91 int t1, t2, i, j, k; 92 cin>>t1; 93 node *root=new node; 94 for(i=1;i<=t1;i++) 95 { 96 scanf("%s",a); 97 insert(root,a,i); 98 } 99 get_fail(root);100 cin>>t2;101 int t=t2;k=1;102 while(t2--){103 memset(visited,0,sizeof(visited));104 scanf("%s",str);105 solve(root,str,k);k++;106 }107 108 int num=0;109 for(i=1;i<=t;i++){110 111 if(!ve[i].empty()){112 sort(ve[i].begin(),ve[i].end());113 printf("web %d:",i);114 for(j=0;j<ve[i].size();j++)115 printf(" %d",ve[i][j]);116 cout<<endl;117 num++;118 }119 }120 printf("total: %d\n",num);121 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。