1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <string.h>  5 #include <string>  6 #include <queue>  7 #include <algorithm>  8 using namespace std;  9 const int N=100005; 10 char str[10005],s1[205]; 11 int ch[N][130]; 12 int val[N],sz,root,fail[N],c=0,viru[N]; 13 bool used[N]; 14 int newnode(){ 15     memset(ch[sz],-1,sizeof(ch[sz])); 16     val[sz]=0; 17     return sz++; 18 } 19 void init(){ 20     sz=0; 21     root=newnode(); 22 } 23 void insert(char* st,int id){ 24     int len=strlen(st); 25     int now=root; 26     for(int i=0;i<len;i++){ 27         int &u=ch[now][st[i]]; 28         if(u==-1)u=newnode(); 29         now=u; 30     } 31     val[now]=id; 32 } 33 void getfail(){ 34     queue<int> q; 35         fail[root] = root; 36         for(int i=0;i<130;i++){ 37             int &u=ch[root][i]; 38             if(u!=-1){ 39                 fail[u]= 0; 40                 q.push(u); 41             } 42             else u=root; 43         } 44     while(!q.empty()){ 45         int now=q.front(); 46         q.pop(); 47         for(int i=0;i<130;i++){ 48             int u=ch[now][i]; 49             if(u==-1)ch[now][i]=ch[fail[now]][i]; 50             else { 51                 fail[u]=ch[fail[now]][i]; 52                 q.push(u); 53             } 54         } 55     } 56 } 57 int  query(char *s){ 58     memset(used,0,sizeof(used)); 59     int len=strlen(s); 60     int now=root; 61     int total=0; 62     for(int i=0;i<len;i++){ 63         now=ch[now][s[i]]; 64         int tem=now; 65         while(tem!=root&&val[tem]&&!used[tem]){ 66             total++; 67             viru[c++]=val[tem]; 68             used[tem]=1; 69             tem=fail[tem]; 70         } 71     } 72     return total; 73 } 74 int main(){ 75     int n,m,i=1; 76     scanf("%d",&n); 77     init(); 78     while(n--){ 79         scanf("%s",s1); 80         insert(s1,i++); 81     } 82     getfail(); 83     scanf("%d",&m); 84     int ans=0; 85     for(int k=1;k<=m;k++){ 86         c=0; 87         scanf("%s",str); 88         int z=query(str); 89         if(z){ 90             ans++; 91             printf("web %d:",k); 92             sort(viru,viru+c); 93             for(int i=0;i<c;i++){ 94                 printf(" %d",viru[i]); 95             } 96             printf("\n"); 97         } 98     } 99     printf("total: %d\n",ans);     //输出”total: 带病毒网站数“    把它看成了所有网站的病毒总数   所以WA了很多次100     return 0;101 }