HDU 2222 Keywords Search (初学AC自动机)
来源：程序员人生 发布时间：2015-03-28 08:17:03 阅读次数：2307次
我是通过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;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
