HDU-2222 Keyword Search

发布时间:2017-4-29 21:35:56 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU-2222 Keyword Search",主要涉及到HDU-2222 Keyword Search方面的内容,对于HDU-2222 Keyword Search感兴趣的同学可以参考一下。

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2222 题目大意: 给你很多个单词,然后给你一篇文章,问给出的单词在文章中出现的次数。 解题思路: AC自动机入门题。需要注意的就是可能有重复单词,坑死人不偿命!~~~~ 代码如下:(红色字体是本人加的并非原文内容!) [cpp] view plaincopy #include<iostream>   #include<cstdio>   #include<cstring>   #include<string>   using namespace std;   #define N 500010   char str[1000010], keyword[51];   int head, tail;      struct node   {       node *fail;       node *next[26];       int count;       node() //初始化,(类似于构造函数)原文是:init     {           fail = NULL;           count = 0;           for(int i = 0; i < 26; ++i)               next[i] = NULL;       }   }*q[N];   node *root;      void insert(char *str) //建立Trie   {       int temp, len;       node *p = root;       len = strlen(str);       for(int i = 0; i < len; ++i)       {           temp = str[i] - 'a';           if(p->next[temp] == NULL)  //防止重复插入             p->next[temp] = new node();           p = p->next[temp];       }       p->count++;   }      void build_ac() //初始化fail指针,BFS   {       q[tail++] = root;  //BFS算法的第一步,根节点入队列     while(head != tail)  //当队列中所有节点都被处理完,head == tail,广搜完成!     {           node *p = q[head++]; //弹出队头 //终于理解了,head指向队列中本次要处理的节点,以此来完成先出!         node *temp = NULL;           for(int i = 0; i < 26; ++i)  //对当前节点的孩子节点进行广度(横向)搜索         {               if(p->next[i] != NULL)  //对有字符的节点建立fail指针             {                   if(p == root) //第一个元素fail必指向根                       p->next[i]->fail = root;                   else                   {                       temp = p->fail; //失败指针  //从要被建立fail指针的节点的父亲节点的失败指针所指的节点开始                     while(temp != NULL) //2种情况结束:匹配为空or找到匹配                       {                           if(temp->next[i] != NULL) //找到匹配                           {                               p->next[i]->fail = temp->next[i];                               break;                           }                           temp = temp->fail;                       }                       if(temp == NULL) //为空则从头匹配                           p->next[i]->fail = root;                   }                              //结束fail指针建立                 q[tail++] = p->next[i]; //入队 //BFS算法的最后一步,将刚才处理完的节点入队列             }           }       }   }      int query() //扫描   {       int index, len, result;       node *p = root; //Tire入口       result = 0;       len = strlen(str);       for(int i = 0; i < len; ++i)       {           index = str[i] - 'a';           while(p->next[index] == NULL && p != root) //跳转失败指针               p = p->fail;           p = p->next[index];           if(p == NULL)               p = root;           node *temp = p; //p不动,temp计算后缀串           while(temp != root && temp->count != -1)           {               result += temp->count;               temp->count = -1;               temp = temp->fail;           }       }       return result;   }      int main()   {       int ncase, num;       scanf("%d", &ncase);       while(ncase--)       {           head= tail = 0;           root = new node();           scanf("%d", &num);           getchar();           for(int i = 0; i < num; ++i)           {               gets(keyword);               insert(keyword);           }           build_ac();           scanf("%s", str);           printf("%d\n", query());       }       return 0;   }  

上一篇:我的extjs聊天机器人(二)
下一篇:多界面 资源异步加载收尾总结

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款