hdu2222Keywords Search

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2222
ac自动机模板题。
刚开始学这个-_-|| 先缓缓。
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<string>
  4 #include<iostream>
  5 const int maxn=500010;
  6 char s[1000010],key[52];
  7 int head,tail;
  8 
  9 struct node
 10 {
 11     node* fail;
 12     node* nex[26];
 13     int ct;
 14     node()
 15     {
 16         fail=NULL;
 17         ct=0;
 18         for(int i=0;i<26;i++)
 19             nex[i]=NULL;
 20     }
 21 };
 22 node* q[maxn];
 23 node* rt;
 24 void inset(char *key)
 25 {
 26     int temp,len;
 27     node* p=rt;
 28     len=strlen(key);
 29     for(int i=0;i<len;i++)
 30     {
 31         temp=key[i]-'a';
 32         if(p->nex[temp]==NULL) p->nex[temp]=new node();
 33         p=p->nex[temp];
 34     }
 35     p->ct++;
 36 }
 37 void getfail()
 38 {
 39     q[tail++]=rt;
 40     while(head!=tail)
 41     {
 42         node* p=q[head++];
 43         node* temp=NULL;
 44         for(int i=0;i<26;i++)
 45         {
 46             if(p->nex[i]!=NULL)
 47             {
 48                 if(p==rt)
 49                     p->nex[i]->fail=rt;
 50                 else
 51                 {
 52                     temp=p->fail;
 53                     while(temp!=NULL)
 54                     {
 55                         if(temp->nex[i]!=NULL){
 56                         p->nex[i]->fail=temp->nex[i];
 57                         break;
 58                         }
 59                         temp=temp->fail;
 60                     }
 61                     if(temp==NULL) p->nex[i]->fail=rt;  //!!!!
 62                 }
 63                 q[tail++]=p->nex[i];
 64             }
 65         }
 66     }
 67 }
 68 int query()
 69 {
 70         int id,len,ans;
 71         node* p=rt;
 72         ans=0;
 73         len=strlen(s);
 74         for(int i=0;i<len;i++)
 75         {
 76             id=s[i]-'a';
 77             while(p->nex[id]==NULL&&p!=rt)
 78                 p=p->fail;
 79             p=p->nex[id];
 80             if(p==NULL)
 81                 p=rt;
 82             node* temp=p;
 83             while(temp!=rt&&temp->ct!=-1)
 84             {
 85                 ans+=temp->ct;
 86                 temp->ct=-1;
 87                 temp=temp->fail;
 88             }
 89         }
 90         return ans;
 91 }
 92 int main()
 93 {
 94     int t;
 95     scanf("%d",&t);
 96     while(t--)
 97     {
 98         int n;
 99         head=tail=0;
100         rt=new node();
101         scanf("%d",&n);
102         for(int i=0;i<n;i++)
103         {
104             scanf("%s",key);
105             inset(key);
106         }
107         getfail();
108         scanf("%s",s);
109         printf("%d
",query());
110     }
111     return 0;
112 }