hdu 2222 Keywords Search

链接：http://acm.hdu.edu.cn/showproblem.php?pid=2222
思路：裸AC自动机，直接贴代码做模板
  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<malloc.h>
  4 #include<queue>
  5 using namespace std;
  6 char str[1000000+100];
  7 
  8 struct node
  9 {
 10     int count;
 11     struct node *next[26];
 12     struct node *fail;
 13     void init()
 14     {
 15         int i;
 16         for(i=0;i<26;i++)
 17             next[i]=NULL;
 18         count=0;
 19         fail=NULL;
 20     }
 21 }*root;
 22 void insert()
 23 {
 24     int len,k;
 25     node *p=root;
 26     len=strlen(str);
 27     for(k=0;k<len;k++)
 28     {
 29         int pos=str[k]-'a';
 30         if(p->next[pos]==NULL)
 31         {
 32             p->next[pos]=new node;
 33             p->next[pos]->init();
 34             p=p->next[pos];
 35         }
 36         else 
 37             p=p->next[pos];
 38     }
 39     p->count++;
 40 }
 41 void getfail()
 42 {
 43     int i;
 44        node *p=root,*son,*temp;
 45        queue<struct node *>que;
 46        que.push(p); 
 47        while(!que.empty())
 48        {
 49            temp=que.front();
 50            que.pop();
 51            for(i=0;i<26;i++)
 52            {
 53                son=temp->next[i];
 54                if(son!=NULL)
 55                {
 56                    if(temp==root) {son->fail=root;}
 57                    else
 58                    {
 59                        p=temp->fail;
 60                        while(p)
 61                        {
 62                            if(p->next[i])
 63                            {
 64                                son->fail=p->next[i];
 65                                break;
 66                            }
 67                            p=p->fail;
 68                        }
 69                        if(!p)  son->fail=root;
 70                    }
 71                    que.push(son);
 72                }
 73            }
 74        }
 75 }
 76 void query()
 77 {
 78     int len,i,cnt=0;
 79     len=strlen(str);
 80     node *p,*temp;
 81     p=root;
 82     for(i=0;i<len;i++)
 83     {
 84         int pos=str[i]-'a';
 85         while(!p->next[pos]&&p!=root)  p=p->fail;      
 86         p=p->next[pos];//
 87         if(!p) p=root;//
 88         temp=p;
 89         /*不要用*temp=*p  因为*p表示一个node，而*temp也表示一个node 但是由于*temp没有分配空间 所以是不能进行赋值的 但是可以用temp指针去指向p*/
 90         while(temp!=root)
 91         {
 92             if(temp->count>=0) 
 93             {
 94                 cnt+=temp->count;
 95                 temp->count=-1;  
 96             }
 97             else break; 
 98             temp=temp->fail; 
 99         }
100     }
101     printf("%d
",cnt);
102 }
103 int main()
104 {
105     int cas,n;
106     scanf("%d",&cas);
107     while(cas--)
108     {
109         root=new node;
110         root->init();
111         root->fail=NULL;
112         scanf("%d",&n);
113         int i;
114         getchar();
115         for(i=0;i<n;i++)
116         {
117             gets(str);
118             insert();
119         }
120         getfail();
121         gets(str);
122         query();
123     }
124     return 0;
125 }