首页 > 代码库 > HDU 3065 (AC自动机模板题)
HDU 3065 (AC自动机模板题)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=3065
题目大意：多个模式串，范围是大写字母。匹配串的字符范围是（0~127）。问匹配串中含有哪几种模式串，且每种模式串出现了多少次。
解题思路：
AC自动机模板题。模式串的范围是大写字母，但是匹配串的范围却是（0~127).
如果Trie 开到 128 加上不回收内存，就会MLE。
实际上开到26就行了，find的时候对于c<0||c>26，强制令pos=root出现失配，并开始下一个字符就行了。
cnt记录这个模式串的个数改为这个模式串的index。
find的时候，把找到的index对应的HASH++，进行统计。
注意每次find时，无须修改last->cnt，因为统计模式串的次数必须让模式串走多遍，修改了之后相当于只走了一遍。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include "cstdio"#include "cstring"#include "string"#include "iostream"#include "queue"#include "vector"#include "algorithm"using namespace std;#define maxn 26int HASH[1050];string code[1050];struct Trie{ Trie *next[maxn],*fail; int cnt;}*root;struct status{ Trie *last; int cnt; status(Trie *last,int cnt):last(last),cnt(cnt) {}};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,int index){ 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=index;}void getfail(){ queue<Trie *> Q; for(int c=0;c<maxn;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<maxn;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]; } }}void find(string str){ Trie *pos=root,*last; queue<status> Q; for(int i=0;i<str.size();i++) { int c=str[i]-‘A‘;last; if(c<0||c>maxn) {pos=root;continue;} if(pos->next[c]) { pos=pos->next[c]; last=pos; while(last->cnt) { Q.push(status(last,last->cnt)); HASH[last->cnt]++; //last->cnt=0; //修改last->cnt last=last->fail; } } }}int main(){ //freopen("in.txt","r",stdin); ios::sync_with_stdio(false); int n,m; string tt; while(cin>>n) { memset(HASH,0,sizeof(HASH)); init(); for(int i=1;i<=n;i++) { cin>>code[i]; Insert(code[i],i); } getfail(); cin>>tt; find(tt); for(int i=1;i<=n;i++) { if(!HASH[i]) continue; cout<<code[i]<<": "<<HASH[i]<<endl; } }}
| 2872067 | neopenx | HDU | 3065 | Accepted | 16056 | 343 | C++ | 2469 | 2014-10-21 16:41:03 |
HDU 3065 (AC自动机模板题)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。