程序员人生 网站导航

HDU 2222 Keywords Search (初学AC自动机)

栏目:综合技术时间:2015-03-28 08:17:03

我是通过http://wenku.baidu.com/view/4e70ccc38bd63186bcebbcb9.html的第2篇学会的

这篇也总结的很好,附带很多经典的习题http://www.cppblog.com/menjitianya/archive/2014/07/10/207604.html

这是bin神的总结:http://www.cnblogs.com/kuangbin/p/3164106.html


这是kss的板子:http://paste.ubuntu.com/10499866/

这个板子用了tire图的优化,即不需要失配回溯,效力大大提高


本题代码:

普通模版:

//826MS 28308K #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; #define MAXN 500500 #define M 1001000 char s[55]; char desc[M]; struct node{ node *next[26]; node *fail; int cnt; }tire[MAXN],*que[MAXN],*root; struct AC { int L,head,tail; node *createnode(){ memset(tire[L].next,0,sizeof(tire[L].next)); tire[L].fail=NULL; tire[L].cnt=0; return &tire[L++]; } void ini(){ L=head=tail=0; root=createnode(); } void Insert(char str[]){ node *cur=root; for(int i=0;str[i];i++){ int val=str[i]-'a'; if(!cur->next[val]){ cur->next[val]=createnode(); } cur=cur->next[val]; } cur->cnt++; } void build(){ que[head++]=root; while(tail<head){ node *cur=que[tail++]; for(int i=0;i<26;i++){ if(cur->next[i]!=NULL){ node *tmp=cur; tmp=tmp->fail; while(tmp!=NULL){ if(tmp->next[i]!=NULL){ cur->next[i]->fail=tmp->next[i]; break; } tmp=tmp->fail; } if(tmp==NULL) cur->next[i]->fail=root; que[head++]=cur->next[i]; } } } } int query(char str[]){ int ans=0; node *cur=root; for(int i=0;str[i];i++){ int val=str[i]-'a'; while(cur!=root&&cur->next[val]==NULL) cur=cur->fail; cur= cur->next[val]; cur=(cur==NULL) ? root:cur; node *tmp = cur; while(tmp!=root){ ans+=tmp->cnt; tmp->cnt=0; tmp=tmp->fail; } } return ans; } }ac; int main(){ int T; scanf("%d",&T); while(T--){ ac.ini(); int m; scanf("%d",&m); while(m--){ scanf("%s",s); ac.Insert(s); } ac.build(); scanf("%s",desc); printf("%d ",ac.query(desc)); } return 0; }

tire图优化模版:(可见效力提高了很多)

//249MS 28308K #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; #define MAXN 500500 #define M 1001000 char s[55]; char desc[M]; struct node{ node *next[26]; node *fail; int cnt; }trie[MAXN],*que[MAXN],*root; struct AC{ int head,tail,L; node* createnode(){ trie[L].fail=NULL; memset(trie[L].next,0,sizeof(trie[L].next)); trie[L].cnt=0; return &trie[L++]; } void ini(){ head=tail=L=0; root=createnode(); } void Insert(char str[]){ node *cur=root; for(int i=0;str[i];i++){ int val=str[i]-'a'; if(cur->next[val]==NULL) cur->next[val]=createnode(); cur=cur->next[val]; } cur->cnt++; } void build(){ que[head++]=root; while(head>tail){ node *cur=que[tail++]; for(int i=0;i<26;i++){ if(cur->next[i]!=NULL){ if(cur==root) cur->next[i]->fail=root; else cur->next[i]->fail=cur->fail->next[i]; que[head++]=cur->next[i]; } else { if(cur==root) cur->next[i]=root; else cur->next[i] = cur->fail->next[i]; } } } } int query(char str[]){ int ans=0; node *cur=root; for(int i=0;str[i];i++){ int val=str[i]-'a'; cur=cur->next[val]; if(cur->cnt){ node *tmp=cur; while(tmp!=root){ ans+=tmp->cnt; tmp->cnt=0; tmp=tmp->fail; } } } return ans; } }ac; int main(){ int T; scanf("%d",&T); while(T--){ ac.ini(); int m; scanf("%d",&m); while(m--){ scanf("%s",s); ac.Insert(s); } ac.build(); scanf("%s",desc); printf("%d ",ac.query(desc)); } return 0; }



------分隔线----------------------------
------分隔线----------------------------

最新技术推荐