HDU 2222 Keywords Search (初學(xué)AC自動(dòng)機(jī))
來(lái)源：程序員人生 發(fā)布時(shí)間：2015-03-28 08:17:03 閱讀次數(shù)：2534次
我是通過(guò)http://wenku.baidu.com/view/4e70ccc38bd63186bcebbcb9.html的第2篇學(xué)會(huì)的
這篇也總結(jié)的很好，附帶很多經(jīng)典的習(xí)題http://www.cppblog.com/menjitianya/archive/2014/07/10/207604.html
這是bin神的總結(jié)：http://www.cnblogs.com/kuangbin/p/3164106.html
這是kss的板子：http://paste.ubuntu.com/10499866/
這個(gè)板子用了tire圖的優(yōu)化，即不需要失配回溯，效力大大提高
本題代碼：
普通模版：
//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圖優(yōu)化模版：（可見(jiàn)效力提高了很多）
//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;
}
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
