UVA10679[I Love Strings!!]

AC自动机再试。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-6-12


DESCRIPTION:


UVa10679


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <string>


using std::string;


#include <list>


using std::list;


 


#include <string.h>


#define H(c) (((c)<=’z’&&(c)>=’a’)?((c)-‘a’):((c)-‘A’+’z’-‘a’+1))


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


#define NODE_SIZE 1000000


#define QUEUE_SIZE 1000000


#define CHECK_SIZE 1000000


#define NEW 1


#define DELETE 2


 


struct node


{


       node* fail;


       node* next[NEXT_SIZE];


       bool end;


};


node* who[CHECK_SIZE];


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,int id)


{


     node* p=root;


     do


     {


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


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


     }


     while (*(++str));


     who[id]=p;


}


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 (char 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)];


               }


           for (char 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)];


               }


     }


}


void 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)


       {


             t->end=true;


             t=t->fail;


       }


     }


     while (*(++str));


}


 


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++)


          {


              cin>>description;


              cin>>N;


              get(NEW);


              node* root=get();


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


              {


                  cin>>keywords;


                  insert(root,keywords.c_str(),j);


              }


              build_ac_automation(root);


              query(root,description.c_str());


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


                  cout<<char(who[j]->end?’y’:’n’)<<endl;


              get(DELETE);


          }


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注