HDU2222[Keywords Search]

AC自动机初试。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-6-12


DESCRIPTION:


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


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <string>


using std::string;


 


#include <string.h>


#define H(c) ((c)-‘a’)


#define NEXT_SIZE (‘z’-‘a’+1)


#define NODE_SIZE 500000


#define QUEUE_SIZE 500000


#define NEW 1


#define DELETE 2


 


struct node


{


       node* fail;


       node* next[NEXT_SIZE];


       int count;


};


node* get(int flag=0)


{


      static node* pool;


      static int top;


      if (!flag)


      {


         memset(pool+top,0,sizeof(node));


         return pool+top++;


      }


      else


      {


         switch (flag)


         {


                case NEW:


                     pool=new node[NODE_SIZE];


                     top=0;


                     break;


                case DELETE:


                     delete[] pool;


                     break;


         }


         return 0;


      }


}


void insert(node* const root,const char* str)


{


     node* p=root;


     do


     {


           if (!p->next[H(*str)]) p->next[H(*str)]=get();


           p=p->next[H(*str)];


     }


     while (*(++str));


     p->count++;


}


void build_ac_automation(node* const root)


{


     static node* q[QUEUE_SIZE];


     node** head;


     node** tail;


     *(head=tail=q)=root;


     while (head<=tail)


     {


           node* qh=*(head++);


           for (int i=’a’;i<=’z’;i++)


               if (qh->next[H(i)])


               {


                  if (qh==root) qh->next[H(i)]->fail=root;


                  else


                  {


                      node* p=qh->fail;


                      while (p)


                      {


                            if (p->next[H(i)])


                            {


                               qh->next[H(i)]->fail=p->next[H(i)];


                               break;


                            }


                            p=p->fail;


                      }


                      if (!p) qh->next[H(i)]->fail=root;


                  }


                  *(++tail)=qh->next[H(i)];


               }


     }


}


int query(node* const root,const char* str)


{


    int result=0;


    node* p=root;


    do


    {


      while (!p->next[H(*str)]&&p!=root) p=p->fail;


      p=p->next[H(*str)];


      if (!p) p=root;


      node* t=p;


      while (t!=root)


      {


            result+=t->count;


            t->count=0;


            t=t->fail;


      }


    }


    while (*(++str));


    return result;


}


 


class Application


{


      int CASE,N;


      string keywords;


      string description;


      public:


      Application()


      {


                   std::ios::sync_with_stdio(false);


                   cin>>CASE;


      }


      int run()


      {


          for (int i=0;i<CASE;i++)


          {


              get(NEW);


              cin>>N;


              node* root=get();


              for (int j=0;j<N;j++)


              {


                  cin>>keywords;


                  insert(root,keywords.c_str());


              }


              build_ac_automation(root);


              cin>>description;


              cout<<query(root,description.c_str())<<endl;


              get(DELETE);


          }


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 

留下评论

电子邮件地址不会被公开。