首页 > 代码库 > HDU 2222（AC自动机模板题)
HDU 2222（AC自动机模板题)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2222
题目大意：多个模式串。问匹配串中含有多少个模式串。注意模式串有重复，所以要累计重复结果。
解题思路：
AC自动机模板题。
一开始使用LRJ的坑爹静态模板，不支持重复的模式串。
在做AC自动机+DP的时候，扒了zcwwzdjn大神的动态优化（失配指向root）写法，以及借鉴了网上的AC自动机模板，
搞出了这么一个支持重复串的模板。
#include "cstdio"#include "cstring"#include "iostream"#include "queue"#include "string"using namespace std;struct Trie{ Trie *next[26],*fail; int cnt;}*root;Trie *newnode(){ Trie *ret=new Trie; memset(ret->next,0,sizeof(ret->next)); ret->fail=0; ret->cnt=0; return ret;}void init() {root=newnode();}void Insert(string str){ Trie *pos=root; for(int i=0;i<str.size();i++) { int c=str[i]-‘a‘; if(!pos->next[c]) pos->next[c]=newnode(); pos=pos->next[c]; } pos->cnt++;}void getfail(){ queue<Trie *> Q; for(int c=0;c<26;c++) { if(root->next[c]) { root->next[c]->fail=root; Q.push(root->next[c]); } else root->next[c]=root; } while(!Q.empty()) { Trie *x=Q.front();Q.pop(); for(int c=0;c<26;c++) { if(x->next[c]) { x->next[c]->fail=x->fail->next[c]; Q.push(x->next[c]); } else x->next[c]=x->fail->next[c]; } }}int find(string str){ Trie *pos=root,*last; int ans=0; for(int i=0;i<str.size();i++) { int c=str[i]-‘a‘;last; if(pos->next[c]) { pos=pos->next[c]; last=pos; while(last->cnt) { ans+=last->cnt; last->cnt=0; last=last->fail; } } } return ans;}int main(){ //freopen("in.txt","r",stdin); ios::sync_with_stdio(false); int T,n; string tt; cin>>T; while(T--) { cin>>n; init(); for(int i=1;i<=n;i++) { cin>>tt; Insert(tt); } getfail(); cin>>tt; int ans=find(tt); printf("%d\n",ans); }}
| 11927003 | 2014-10-21 01:22:37 | Accepted | 2222 | 390MS | 29480K | 1942 B | C++ | Physcal |
HDU 2222（AC自动机模板题)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。