hdu3065

题意：给出n个病毒串（模式串），再给出一个待匹配串，问每种模式串在其中出现了几次，0次不输出

也是将AC自动机的模板稍微修改了一下，由于每个模式串都不同，所以直接用cnt数组记录结点代表的模式串的标号，在匹配串时计数就可以了

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int maxm=1010*55; 6  7 char s[2000000+50],word[1010][55]; 8 int c; 9 int vis[1010];10 int nxt[maxm][128-30],cnt[maxm],fail[maxm],size;11 12 int newnode(){13     memset(nxt[size],0,sizeof(nxt[size]));14     fail[size]=cnt[size]=0;15     return size++;16 }17 18 void insert(char s[],int k){19     int i,p=0;20     for(i=0;s[i];i++){21         int &x=nxt[p][s[i]-30];22         p=x?x:x=newnode();23     }24     cnt[p]=k;25 }26 27 void makenxt(){28     int i;29     queue
         
          q;30     q.push(0);31     while(!q.empty()){32         int u=q.front();33         q.pop();34         for(i=0;i<128-30;i++){35             int v=nxt[u][i];36             if(v==0)nxt[u][i]=nxt[fail[u]][i];37             else q.push(v);38             if(u&&v){39                 fail[v]=nxt[fail[u]][i];40             }41         }42     }43 }44 45 void query(char s[]){46     int d=0;47     for(int i=0;s[i];i++){48         d=nxt[d][s[i]-30];49         int tmp=d;50         while(tmp!=0){51             vis[cnt[tmp]]++;52             tmp=fail[tmp];53         }54     }55 }56 57 int main(){58     int n;59     while(scanf("%d",&n)!=EOF){60         size=0,newnode();61         int i;62         memset(cnt,0,sizeof(cnt));63         memset(vis,0,sizeof(vis));64         for(i=1;i<=n;i++){65             scanf("%s",word[i]);66             insert(word[i],i);67         }68         makenxt();69         scanf("%s",s);70         query(s);71         for(i=1;i<=n;i++){72             if(vis[i])printf("%s: %d\n",word[i],vis[i]);73         }74     }75     return 0;76 }