注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

HDU2222[Keywords Search]  

2010-06-13 14:33:47|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

}

 

  评论这张
 
阅读(258)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018