首页 > 代码库 > xtu字符串 D. 病毒侵袭
xtu字符串 D. 病毒侵袭
D. 病毒侵袭
Time Limit: 1000ms
Memory Limit: 32768KB
64-bit integer IO format: %I64d Java class name: Main当太阳的光辉逐渐被月亮遮蔽,世界失去了光明,大地迎来最黑暗的时刻。。。。在这样的时刻,人们却异常兴奋——我们能在有生之年看到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
解题:AC自动机的模板题。。。。哎。。。改了一天。。。。终于满意了。。。。。。。。。。。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <vector> 6 #include <climits> 7 #include <algorithm> 8 #include <cmath> 9 #include <queue> 10 #define LL long long 11 #define INF 0x3f3f3f 12 using namespace std; 13 const int maxn = 100000; 14 struct trie { 15 int cnt,id,wd[130],fail; 16 void init() { 17 id = cnt = 0; 18 fail = -1; 19 memset(wd,-1,sizeof(wd)); 20 } 21 } dic[maxn]; 22 int tot,ans[1100],total; 23 void insertWord(int root,int _id,char *s) { 24 for(int i = 0; s[i]; i++) { 25 int k = s[i] - 31; 26 if(dic[root].wd[k] == -1) { 27 dic[tot].init(); 28 dic[root].wd[k] = tot++; 29 } 30 root = dic[root].wd[k]; 31 } 32 dic[root].cnt++; 33 dic[root].id = _id; 34 } 35 void build(int root) { 36 queue<int>q; 37 q.push(root); 38 while(!q.empty()) { 39 int u = q.front(); 40 q.pop(); 41 for(int i = 0; i < 130; i++) { 42 if(dic[u].wd[i] == -1) continue; 43 if(!u) dic[dic[u].wd[i]].fail = 0;//如果是第二层的节点 44 else { 45 int v = dic[u].fail; 46 while(v && dic[v].wd[i] == -1) 47 v = dic[v].fail; 48 //回溯到离根较远并与当前字符相同的点 49 if(dic[v].wd[i] != -1) 50 dic[dic[u].wd[i]].fail = dic[v].wd[i]; 51 else dic[dic[u].wd[i]].fail = 0; 52 } 53 q.push(dic[u].wd[i]); 54 } 55 } 56 } 57 58 void query(int root,char *s) { 59 bool vis[510] = {false}; 60 for(int i = 0; s[i]; i++) { 61 int k = s[i] - 31; 62 while(root && dic[root].wd[k] == -1) 63 root = dic[root].fail;//不如当前字符匹配,回溯 64 root = dic[root].wd[k];//dic[root].wd[k]与当前字符匹配 65 if(root == -1) root = 0;//trie树上不存在与之匹配的 66 else { 67 int v = root; 68 while(v && !vis[dic[v].id]) { 69 //如果当前节点访问过了, 70 //从当前节点的回溯路径上的节点也被访问了 71 if(dic[v].cnt) { 72 vis[dic[v].id] = true; 73 ans[total++] = dic[v].id; 74 } 75 v = dic[v].fail; 76 } 77 } 78 } 79 } 80 int main() { 81 int n,m,i,j,t = 0; 82 char word[300],text[11000]; 83 scanf("%d",&n); 84 dic[0].init(); 85 tot = 1; 86 for(i = 1; i <= n; i++) { 87 scanf("%s",word); 88 insertWord(0,i,word); 89 } 90 build(0); 91 scanf("%d",&m); 92 for(i = 1; i <= m; i++) { 93 total = 0; 94 scanf("%s",text); 95 query(0,text); 96 if(total) { 97 t++; 98 sort(ans,ans+total); 99 printf("web %d:",i);100 for(j = 0; j < total; j++)101 printf(" %d",ans[j]);102 printf("\n");103 }104 }105 printf("total: %d\n",t);106 return 0;107 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。