- 浏览: 377483 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
wsyzyrxp:
非常感谢 兄弟 帮了我大忙
[opengl]弹簧质点法模拟柔性布料以及椭球碰撞的opengl实现 -
mingdry0304:
[opengl]彩色立方体旋转 -
tyfengyu:
我刚刚更改的代码加上了标准差stdVal,故recoMat应该 ...
[python]用python实现的pca算法 -
tyfengyu:
python的pca代码有2处错误:1.finalData = ...
[python]用python实现的pca算法 -
暴风雪:
McFlurry 写道前排(凑字数)!擦你怎么摸来这里的
诈尸总结
大致题意:
给出n个模式串(长度不超过50),和一个文本串(长度不超过1000000),求出有多少个模式串在这个文本串中出现过。
大致思路:
标准的AC自动机问题,主要是学习模版,理解自动机的匹配机制。
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include <algorithm> using namespace std; const int inf=1<<28; const int nMax=500; const int mMax=500005; class node{ public: int id; int vis; //前缀记录标志 node *next[26],*fail; node(){ vis=0; fail=NULL; for(int i=0;i<26;i++)next[i]=NULL; } }*root,*que[mMax]; void insert(char *s){ //构造前缀树 int i; node *r=root; int l=strlen(s); for(i=0;i<l;i++){ int loc=s[i]-'a'; if(r->next[loc]==NULL){ r->next[loc]=new node(); } r=r->next[loc]; } r->vis++; } void acAuto(){ //用bfs为每个节点设定fail指针 int i,head=0,tail=0; node *p,*tmp; root->fail=NULL; que[tail++]=root; while(head<tail){ tmp=que[head++]; for(i=0;i<26;i++){ if(tmp->next[i]==NULL)continue; if(tmp==root){ tmp->next[i]->fail=root; } else { for(p=tmp->fail;p!=NULL;p=p->fail){ if(p->next[i]!=NULL){ tmp->next[i]->fail=p->next[i]; break; } } if(p==NULL){ tmp->next[i]->fail=root; } } que[tail++]=tmp->next[i]; } } } int search(char *msg){ int i,idx,ans=0; node *p=root,*tmp; for(i=0;msg[i];i++){ idx=msg[i]-'a'; while(p->next[idx]==NULL&&p!=root){ p=p->fail; } p=p->next[idx]; if(p==NULL)p=root; for(tmp=p;tmp!=NULL&&tmp->vis!=-1;tmp=tmp->fail){ ans+=tmp->vis; tmp->vis=-1; } } return ans; } int main(){ int cas,n,i; char str[52],text[1000002]; scanf("%d",&cas); while(cas--){ scanf("%d",&n); root=new node(); while(n--){ scanf("%s",str); insert(str); } acAuto(); scanf("%s",text); printf("%d\n",search(text)); } return 0; }
另附上静态tire树版本,可以省去不少生成新对象的时间(动态250ms,静态180)
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include <algorithm> using namespace std; const int inf=1<<28; const int nMax=500; const int mMax=500005; class node{ public: int id; int vis; //前缀记录标志 node *next[26],*fail; // node(){ // vis=0; // fail=NULL; // for(int i=0;i<26;i++)next[i]=NULL; // } }*root,*que[mMax],num[5000000]; int x; node *newnode(){ node * p = num + x++; for(int i = 0; i <26; i++){ p->next[i] = NULL; } p->fail=NULL; p->vis=0; return p; } void insert(char *s){ //构造前缀树 int i; node *r=root; int l=strlen(s); for(i=0;i<l;i++){ int loc=s[i]-'a'; if(r->next[loc]==NULL){ r->next[loc]=newnode(); } r=r->next[loc]; } r->vis++; } void acAuto(){ //用bfs为每个节点设定fail指针 int i,head=0,tail=0; node *p,*tmp; root->fail=NULL; que[tail++]=root; while(head<tail){ tmp=que[head++]; for(i=0;i<26;i++){ if(tmp->next[i]==NULL)continue; if(tmp==root){ tmp->next[i]->fail=root; } else { for(p=tmp->fail;p!=NULL;p=p->fail){ if(p->next[i]!=NULL){ tmp->next[i]->fail=p->next[i]; break; } } if(p==NULL){ tmp->next[i]->fail=root; } } que[tail++]=tmp->next[i]; } } } int search(char *msg){ int i,idx,ans=0; node *p=root,*tmp; for(i=0;msg[i];i++){ idx=msg[i]-'a'; while(p->next[idx]==NULL&&p!=root){ p=p->fail; } p=p->next[idx]; if(p==NULL)p=root; for(tmp=p;tmp!=NULL&&tmp->vis!=-1;tmp=tmp->fail){ ans+=tmp->vis; tmp->vis=-1; } } return ans; } int main(){ int cas,n,i; char str[52],text[1000002]; scanf("%d",&cas); while(cas--){ x=0; scanf("%d",&n); root=newnode(); while(n--){ scanf("%s",str); insert(str); } acAuto(); scanf("%s",text); printf("%d\n",search(text)); } return 0; }
发表评论
-
[树状数组]poj 2299
2014-12-13 20:58 1872题意 求一列数字的逆序数。 思路 ... -
[树状数组]hdoj 1166
2014-12-12 01:21 2题意 http://acm.hdu.edu.cn/ ... -
[树状数组]hdoj 1166
2014-12-12 01:21 846题意 http://acm.hdu.edu.cn/ ... -
[离散化+线段树]poj2528
2014-12-01 23:16 579题意 给出每个海报的位置,问最后没有被完全覆盖 ... -
[线段树区间合并]poj 3667
2014-12-01 11:45 750i题意 和poj1823差不多,加了一个查 ... -
[线段树区间更新]poj 1823
2014-12-01 02:56 847题意 一个旅馆有n个房间,有m次操作,每次操作可 ... -
[线段树]poj 3368
2014-11-29 07:58 695题意 给出一串数字,有m次询问,每次询问[ab ... -
[线段树成段更新]poj 2777
2014-11-28 01:33 1087题意: 一段区间从1-n的初始颜色为1,每 ... -
[线段树]poj 2182
2014-11-27 23:13 578题意: n头牛站队,每头牛都有一个属于[ ... -
[线段树]poj 3264
2014-11-27 21:57 466题意 给出一串数字,m个询问,对于每次询问求出 ... -
[线段树成段更新]hdoj 1698
2014-11-27 21:00 684题意: 对一个线段上的值进行修改,一次可以把[i, ... -
[线段树成段更新]poj 3468
2014-11-27 12:43 661题意: 给出一串n个数,每次操作分为两种,分 ... -
[线段树]poj 2828
2014-11-26 22:02 686题意 n个人插队,每次某个人都会选择插入第i个 ... -
[线段树]hdoj 2795
2014-11-25 20:33 830题意:一个高h宽w的二维空间,每次放进去一个高为1,宽为a的 ... -
[线段树]hdoj 1394
2014-11-24 22:40 892题意 给出一列n个数字,每一个数字都和其他 ... -
[后缀数组]acdream 1430
2014-10-16 14:08 501大致题意: 求出一个字符串(len<=1 ... -
[KMP+乱搞]hdoj 4749
2014-10-11 15:22 741大致题意: 求文本串中最多能选出多少子串,使得这 ... -
[KMP]hdoj 4763
2014-10-10 11:39 657题意: 给出一个字符串,问是否存在这样的子串E使得 ... -
[后缀数组][二分]hdu 5008
2014-09-27 10:10 975大致题意: 给出一个长度小于100000的字符串 ... -
[线段树,单点更新]hdoj 1754:I Hate It
2012-10-21 21:33 1223大致题意: 给出一个数组,在线更新点的值,查询区 ...
相关推荐
多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 ...
供信息学奥林匹克竞赛选手使用 AC自动机模板
要学AC自动机需要自备两个前置技能:KMP和trie树(其实个人感觉不会kmp也行,失配指针的概念并不难) 其中,KMP是用于一对一的字符串匹配,而trie虽然能用于多模式匹配,但是每次匹配失败都需要进行回溯,如果模式串很长的话...
基于单模式串和 Trie 树实现的敏感词过滤我们前面几节讲了好几种字符串匹配算法,有 BF 算法、RK 算法、BM 算法、KMP 算法,前面四种算法都是单模式串
AC自动机算法(Aho-Corasick 多模式匹配算法)C#实现
AC自动机AC自动机AC自动机AC自动机
AC自动机算法是解决这种问题的一个经典方法,时间复杂度为O(n+m+z),其中z是T中出现的模式串的数量。AC自动机是基于keyword tree的,并对其进行一些补充。
相当给力,头文件中附带了简单的使用方法,使用istream当接口,因此你可以传入stringstream或fstream,甚至可以自己派生istream再传入,支持全文查找和增量查找两种模式,有问题可以联系我
AC自动机算法
AC自动机算法的实现。AC自动机:Aho-Corasick automation,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法之一。一个常见的例子就是给出n个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章...
关于AC自动机的pdf文档,很清楚的讲解了AC自动机算法及应用
C语言实现,效率极高,实现了中文的关键字匹配,输出的格式为偏移量加上关键字(中文编码为GB2312)
关于AC自动机的详细的讲解+标程,还有一些例题的讲解。
本项目是一款高效的Java敏感词过滤系统,基于AC自动机算法实现。系统支持独立部署,同时可便捷集成至注册中心,为各类项目提供敏感词过滤服务。包含文件共117个,其中主要构成如下: - Java源文件:49个 - Class...
AC自动机实现多模式串匹配,支持中文系统,同时可以支持多个模式串,测试使用Linux和Windows系统,使用20条模式串,中英文混合,测试通过
文学研究助手,AC自动机版本,数据结构 利用AC自动机只对文件进行一次扫描,统计要查询的单词在文档出现的次数及所在行
AC自动机模板,直接套,有注释N的范围,适合初学者学习
基于字典树的ac自动机,自己前期的实现,具有源码参考,用于查找可屏蔽应用
中文AC自动机,可以用于中文字符串,可以结合中文分词使用
AC自动机最全数据,大家可以看一下,欢迎下载,谢谢支持!!!!!!!!!!!!!!!!!!!!!!!!