病毒侵袭
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6515 Accepted Submission(s): 1721
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
Recommend
gaojie
#include<iostream> #include<cstdio> #include<cstring> /* 寻找都有哪些子串 不能保证是字母或数字，所以子节点有差不多130个 */ using namespace std; const int N=130; int n,m,tag[520]; struct Trie{ int count; //是否为该单词的最后一个节点 Trie *fail; //失败指针 Trie *next[N]; Trie(){ //构造函数初始化 count=0; fail=NULL; memset(next,NULL,sizeof(next)); } }*q[5000010]; //队列，方便用于bfs构造失败指针 char word[520]; //输入的单词 char str[1000010]; //模式串 int head,tail; //队列的头尾指针 void Insert(char *str,Trie *Root,int id){ Trie *loc=Root; int i=0; while(str[i]!='\0'){ int id=str[i]-31; if(loc->next[id]==NULL) loc->next[id]=new Trie(); loc=loc->next[id]; i++; } loc->count=id; //初始化为0，++后为1，表示是一个单词的结尾 } void AC_automation(Trie *Root){ Root->fail=NULL; q[head++]=Root; Trie *cur,*tmp; while(head!=tail){ cur=q[tail++]; //拿到一个节点 tmp=NULL; for(int i=0;i<N;i++){ if(cur->next[i]!=NULL){ //若其i孩子非空 if(cur==Root) //他自己是头，其孩子的失败指针指向头 cur->next[i]->fail=Root; else{ //普通节点 tmp=cur->fail; //指向自己的失败指针 while(tmp!=NULL){ if(tmp->next[i]!=NULL){ //失败指针有i孩子 cur->next[i]->fail=tmp->next[i]; //当前节点的i孩子的失败指针指向失败指针的i孩子，然后跳出 break; } tmp=tmp->fail; //继续找失败指针 } if(tmp==NULL) //若失败指针为空 cur->next[i]->fail=Root; //当前节点的i孩子的失败指针指向头 } q[head++]=cur->next[i]; //进去的都是定义过失败指针的,故此过程是给其孩子定义失败指针 } } } } int query(Trie *Root){ int i=0,cnt=0; Trie *loc=Root,*tmp; while(str[i]!='\0'){ int id=str[i]-31; //计算孩子的位置 while(loc->next[id]==NULL && loc!=Root){ loc=loc->fail; //若没有i孩子节点，通过失败指针找与这之前相同的有i孩子的节点 } loc=loc->next[id]; //指向其i孩子 loc=(loc==NULL)?Root:loc; tmp=loc; while(tmp!=Root && tmp->count!=0){ if(tmp->count!=0 && !tag[tmp->count]){ //主要是改这里 cnt++; tag[tmp->count]=1; } tmp=tmp->fail; } i++; } return cnt; } int main(){ //freopen("input.txt","r",stdin); //int n,m; while(scanf("%d",&n)!=EOF){ head=tail=0; Trie *Root=new Trie(); getchar(); for(int i=1;i<=n;i++){ gets(word); Insert(word,Root,i); } AC_automation(Root); scanf("%d",&m); int total=0; for(int i=1;i<=m;i++){ memset(tag,0,sizeof(tag)); scanf("%s",str); int flag=query(Root); if(flag){ printf("web %d:",i); for(int j=1;j<=n;j++) if(tag[j]) printf(" %d",j); printf("\n"); total++; } } printf("total: %d\n",total); } return 0; }