病毒侵袭
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 25665 Accepted Submission(s): 6055
Problem Description 当太阳的光辉逐渐被月亮遮蔽，世界失去了光明，大地迎来最黑暗的时刻。。。。在这样的时刻，人们却异常兴奋——我们能在有生之年看到500年一遇的世界奇观，那是多么幸福的事儿啊~~ 但网路上总有那么些网站，开始借着民众的好奇心，打着介绍日食的旗号，大肆传播病毒。小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码可见字符（不包括回车）。
Output 依次按如下格式输出按网站编号从小到大输出，带病毒的网站编号和包含病毒编号，每行一个含毒网站信息。 web 网站编号: 病毒编号 病毒编号 … 冒号后有一个空格，病毒编号按从小到大排列，两个病毒编号之间用一个空格隔开，如果一个网站包含病毒，病毒数不会超过3个。 最后一行输出统计信息，如下格式 total: 带病毒网站数 冒号后有一个空格。
Sample Input 3 aaa bbb ccc 2 aaabbbccc bbaacc
Sample Output web 1: 1 2 3 total: 1
Source 2009 Multi-University Training Contest 10 - Host by NIT
题意：给你一堆病毒，每个病毒用一个字符串表示，然后给你几个网站，网站也由一个字符串表示，问你每个网站中含有多少个病毒，并把这些病毒按编号从小到大输出来，最后输出含有病毒的网站总数。
解题思路：直接ac自动机模板即可，需要注意的是这题如果用g++提交可能会超内存，用c++提交。
#include<iostream> #include<stdio.h> #include<cstring> #include<queue> #include<algorithm> using namespace std; int N,M; int cnt; int num; int result[1000]; char ch[10010]; bool visit[1000]; struct node{ node *next[130]; node *fail; int id; }; node *root; node *newnode; node Tree[100010]; node* getNode() { return &Tree[num++]; } void Insert(char *s,int id) { node *p = root; int len = strlen(s); for(int i = 0; i < len; i++) { int x = s[i] - ' '; if(p->next[x] == NULL) { newnode = getNode(); for(int j = 0; j < 130; j++) newnode->next[j] = NULL; newnode->fail = 0; newnode->id = -1; p->next[x] = newnode; } p = p->next[x]; } p->id = id; } void build_fail_pointer() { queue<node*> Q; node *term; node *ans; while(!Q.empty()) Q.pop(); Q.push(root); while(!Q.empty()) { term = Q.front(); Q.pop(); for(int i = 0; i < 130; i++) { if(term->next[i]) { if(term == root) { term->next[i]->fail = root; } else { ans = term->fail; while(ans&&ans->next[i] == NULL) ans = ans->fail; if(ans == NULL) term->next[i]->fail = root; else term->next[i]->fail = ans->next[i]; } Q.push(term->next[i]); } } } } int ac_automation(char *s) { cnt = 0; for(int i = 0; i < 1000; i++) visit[i] = false; node *p = root; node *term; int len = strlen(s); for(int i = 0; i < len; i++) { int x = s[i] - ' '; while(p&&p->next[x] == NULL) p = p->fail; if(p == NULL) p = root; p = p->next[x]; if(p) { term = p; while(term) { if(term->id != -1) { if(!visit[term->id]) { result[++cnt] = term->id; visit[term->id] = true; } //term->id = -1; } term = term->fail; } } } return cnt; } int main() { while(~scanf("%d",&N)) { num = 0; root = getNode(); for(int j = 0; j < 130; j++) root->next[j] = NULL; root->fail = 0; root->id = -1; int total = 0; for(int i = 1; i <= N; i++) { scanf("%s",ch); Insert(ch,i); } build_fail_pointer(); scanf("%d",&M); for(int i = 1; i <= M; i++) { scanf("%s",ch); int x = ac_automation(ch); if(x == 0) continue; else { total++; sort(result + 1,result + x + 1); printf("web %d:",i); for(int j = 1; j <= x; j++) { printf(" %d",result[j]); } printf("\n"); //total += x; } } printf("total: %d\n",total); } return 0; }