hdu 2896 ( 病毒侵袭 )

 先学习了一下ac 自动机 http://www.cppblog.com/mythit/archive/2009/04/21/80633.html

关键的几句话 ：buildac  构造失败指针的过程概括起来就一句话：设这个节点上的字母为C，沿着他父亲的失败指针走，直到走到一个节点，他的儿子中也有字母为C的节点。然后把当前节点的失败指针指向那个字母也为C的儿子。如果一直走到了root都没找到，那就把失败指针指向root。

query  当前字符匹配，表示从当前节点沿着树边有一条路径可以到达目标字符，此时只需沿该路径走向下一个节点继续匹配即可，目标字符串指针移向下个字符继续匹配；(2)当前字符不匹配，则去当前节点失败指针所指向的字符继续匹配，匹配过程随着指针指向root结束。重复这2个过程中的任意一个，直到模式串走到结尾为止。

#include <iostream> 
#include<string.h>
using namespace std; 
   
 const int kind =128;
 int ans[503]; 
 int total;
 struct node{  
     node *fail;      
     node *next[kind]; 
     int count;        
     node(){  
         count=0;
         fail=NULL; 
         memset(next,NULL,sizeof(next)); 
     } 
 }*q[500001];          
   
 void insert(char *str,node *root,int w){ 
     node *p=root; 
     int i=0,index;  
     while(str[i]){ 
         index=str[i]; 
         if(p->next[index]==NULL) p->next[index]=new node();  
         p=p->next[index];
         i++;
     } 
     p->count=w; 
 } 

 void buildac(node *root)
 {
     
     node *temp,*p;
     int i,front=0,rear=0;
     q[rear++]=root;
     while(rear>front)
     {
         p=q[front++];
         for(i=0;i<kind;i++)
         {
             if(p->next[i]!=NULL)
             {
                 if(p==root)
                     p->next[i]->fail=root;
                 else
                 {
                     temp=p->fail;
                     /*while(temp->next[i]==NULL&&temp!=root)   // 错误
                         temp=temp->fail;
                     p->next[i]->fail=temp->next[i];
                     if(temp==root)
                         p->next[i]->fail=root;*/
                     while(temp!=NULL)
                     {
                         if(temp->next[i]!=NULL)
                         {
                             p->next[i]->fail=temp->next[i];
                             break;
                         }
                         temp=temp->fail;
                     }
                     if(temp==NULL)
                         p->next[i]->fail=root;

                 }
                 q[rear++]=p->next[i];
             }
         }
     }
 }

 void query(node *root,char *ss,int n)
 {
     int i,flag=0;
     node *temp,*p;
     p=root;
     for(i=0;ss[i]!='\0';i++)
     {
         while(p->next[ss[i]]==NULL&&p!=root)
             p=p->fail;
         p=p->next[ss[i]];
         if(p==NULL)
             p=root;
         temp=p;
         while(temp!=root)
         {
             if(temp->count)
             {
                 flag=1;
                 ans[temp->count]=1;
             }
             temp=temp->fail;
         }
     }
     if(flag==1)
     {
         total++;
         printf("web %d:",n);
     }
     for(i=0;i<=501;i++)
         if(ans[i])
             printf(" %d",i);
         if(flag==1)
         printf("\n");
 }

 int main()
 {
     node *root;
     char s[203],ss[10010];
     int i,n,m;
     while(scanf("%d",&n)!=EOF)
     {
         total=0;
         root=new node();
         for(i=1;i<=n;i++)
         {
             scanf("%s",s);
             insert(s,root,i);
         }
         buildac(root);
         scanf("%d",&m);
         for(i=1;i<=m;i++)
         {
             scanf("%s",ss);
             memset(ans,0,sizeof(ans));
             query(root,ss,i);
         }
         printf("total: %d\n",total);
     }
     return 0;
 }