HDU 2896

AC自动机简单题
  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("
");
 97         }
 98     }
 99     printf("total: %d
",ans);     //输出”total: 带病毒网站数“    把它看成了所有网站的病毒总数   所以WA了很多次
100     return 0;
101 }