hdoj 2222Keywords Search解题报告

链接：http://acm.hdu.edu.cn/showproblem.php?pid=2222

AC自动机，用于这种在一个串中同时查找几个子串的出现个数，这是一道模板题，所以很有保存的价值，具体的ac自动机的匹配原理http://www.cppblog.com/mythit/archive/2009/04/21/80633.html

View Code

  1 #include<stdio.h>
  2 #include<string.h>
  3 struct node
  4 {
  5     int cnt;
  6     node *next[26],*fail;
  7 }*rt,qq[500005],*que[500005];//不去新建节点，而是用qq数组去存储，节省时间
  8 char key[55];
  9 char mes[1000005];
 10 int k;
 11 void insert(char *str)//创建字典树的过程
 12 {
 13     int i;
 14     int temp;
 15     node *p=rt;
 16     for(i=0;str[i];i++)
 17     {
 18         temp=str[i]-'a';
 19         if(p->next[temp]==NULL)
 20         {
 21             qq[k].cnt=0;
 22             qq[k].fail=NULL;
 23             memset(qq[k].next,NULL,sizeof(qq[k].next));
 24             p->next[temp]=&qq[k++];
 25         }
 26         p=p->next[temp];
 27     }
 28     p->cnt++;
 29 }
 30 void ac()//类似于kmp的getnext函数
 31 {
 32     int f=0,r=0;
 33     int i;
 34     node *p,*temp;
 35     rt->fail=NULL;
 36     que[r++]=rt;
 37     while(f<r)
 38     {
 39         temp=que[f++];
 40         for(i=0;i<26;i++)
 41         {
 42             if(temp->next[i]==NULL)
 43             continue;
 44             if(temp==rt)
 45             temp->next[i]->fail=rt;
 46             else
 47             {
 48                 for(p=temp->fail;p!=NULL;p=p->fail)
 49                 {
 50                     if(p->next[i]!=NULL)
 51                     {
 52                         temp->next[i]->fail=p->next[i];
 53                         break;
 54                     }
 55                 }
 56                 if(p==NULL)
 57                 {
 58                     temp->next[i]->fail=rt;
 59                 }
 60             }
 61             que[r++]=temp->next[i];
 62         }
 63     }
 64 }
 65 int acs()
 66 {
 67     int ans=0;
 68     int i,id;
 69     node *p=rt,*temp;
 70     for(i=0;mes[i];i++)
 71     {
 72         id=mes[i]-'a';
 73         while(p->next[id]==NULL&&p!=rt)
 74         p=p->fail;
 75         p=p->next[id];
 76         if(p==NULL)
 77         p=rt;
 78         for(temp=p;temp!=NULL&&temp->cnt!=-1;temp=temp->fail)
 79         {
 80             ans+=temp->cnt;
 81             temp->cnt=-1;
 82         }
 83     }
 84     return ans;
 85 }
 86 int main()
 87 {
 88     int t;
 89     scanf("%d",&t);
 90     int n;
 91     int i,j;
 92     while(t--)
 93     {
 94         k=0;
 95         rt=&qq[k++];
 96         memset(rt->next,NULL,sizeof(rt->next));
 97         scanf("%d",&n);
 98         for(i=0;i<n;i++)
 99         {
100             scanf("%s",key);
101             insert(key);
102         }
103         ac();
104         scanf("%s",mes);
105         printf("%d\n",acs());
106     }
107     return 0;
108 }