hdu2222 key word search
模板题来的，求所有单词在文本的出现的个数
简单说说我对AC自动机的理解吧
学习AC自动机的之前，首先要了解的就是kmp
kmp处理的是单个模式串与文本的匹配，其中kmp的关键就在于求next数组，而且next数组记录的就是，如果当前位置匹配失败的，模式串应该应该移动到哪一个位置重新与文本匹配，这样就避免了每次都从头开始匹配，而且文本串的指针是不需要回溯的
对于AC自动机也是类似，充分利用已匹配的信息，避免了从头开始匹配。AC自动机处理的是多个模式串与一个文本，最糟糕的情况就是我们用每一个模式串跟文本进行匹配。但是，当前一个模式串匹配失败时，是否有什么信息可以被下一个模式串利用呢？答案是有的，fail指针的作用类似与next数组。
该算法主要分三步：
第一：对所有的模式串构建一棵trie树，这个比较简单
第二：构造trie树上所有节点的fail指针，fail指针指向的是：如果当前节点匹配失败，则从另一个模式串开始匹配，此时对于新开始的位置必有：所在模式串的前缀是转移前的节点所在串的子串（而且已经匹配成功的部分）
第三：将文本在模式串上进行匹配，匹配过程主要有俩个操作：1）如果匹配成功，则沿着树边有一条路径可以到达目标字符，此时只需沿该路径走向下一个节点继续匹配即可；2）匹配失败，则转移到失败指针所指的节点继续匹配。。 重复则俩个操作直至文本结束
具体的可以参见大牛的博客，写得很详细，学到了很多东西http://www.cppblog.com/mythit/archive/2009/04/21/80633.html
用静态数组保存字典树
#include <stdio.h>
#include <stdlib.h>
int const N= 500010;
struct Trie{
int flag; // 标记是否为某一模式串的结尾
int fail; // 失败指针
int next[26];
void init(){
flag= 0; fail= -1;
for( int i= 0; i< 26; ++i )
next[i]= 0; }
}tb[N];
int cnt= 0, que[N], n;
char str[1000010];
void inline insert( char* s ){
int rt= 0;
while( *s ){
int t= *s- 'a';
if( !tb[rt].next[t] ){
tb[++cnt].init();
tb[rt].next[t]= cnt;
}
rt= tb[rt].next[t]; s++;
}
tb[rt].flag++;
}
void bfs(){
int head= 0, tail= 0, p, q;
que[0]= 0;
while( head<= tail ){
int now= que[head++];
for( int t= 0; t< 26; ++t )
if( tb[now].next[t] ){
p= tb[now].fail, q= tb[now].next[t];
while( p!= -1 && !tb[p].next[t] ) p= tb[p].fail;
if( p== -1 ) tb[q].fail= 0;
else tb[q].fail= tb[p].next[t];
que[++tail]= q;
}
}
}
void Match( char* s ){
int ans= 0, rt= 0, t, p;
while( *s ){
t= *s- 'a';
if( tb[rt].next[t] ) rt= tb[rt].next[t];
else{
p= tb[rt].fail;
while( p!= -1 && !tb[p].next[t] ) p= tb[p].fail;
if( p== -1 ) rt= 0;
else rt= tb[p].next[t];
}
p= rt;
while( p!= 0 && tb[p].flag ){
if( tb[p].flag ){
ans+= tb[p].flag; tb[p].flag= 0; }
p= tb[p].fail;
}
s++;
}
printf("%d\n", ans );
}
int main(){
int test;
scanf("%d",&test );
while( test-- ){
scanf("%d\n",&n );
cnt= 0; tb[0].init();
while( n-- ){
gets(str);
insert( str );
}
bfs();
gets(str);
Match( str );
}
return 0;
}
动态节点保存字典树
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int kind = 26;
struct node
{
node *fail;//失败指针
node *next[kind];
int count;//单词结尾的标记
node(){//构造函数初始化
fail=NULL;
count=0;
memset(next,NULL,sizeof(next));
}
}*q[500001];//队列，在构造失败指针时用
char keyword[51];//输入的单词
char str[1000001];//模式串
int head,tail;
void insert(char *str,node *root)//为单词构造trie树，
{
node *p=root;
int i=0,index;
while(str[i])
{
index=str[i]-'a';
if(p->next[index]==NULL)
p->next[index]=new node();
p=p->next[index];
i++;
}
p->count++;//单词结尾
}
void build_ac_automation(node *root)
{
int i;
head=tail=0;
root->fail=NULL;
q[head++]=root;
while(head!=tail)
{
node *temp=q[tail++];
node *p=NULL;
for(i=0;i<kind;i++)
{
if(temp->next[i]!=NULL)
{
if(temp==root)temp->next[i]->fail=root;
else{
p=temp->fail;
while(p!=NULL)
{
if(p->next[i]!=NULL)
{
temp->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
if(p==NULL) temp->next[i]->fail=root;
}
q[head++]=temp->next[i];
}
}
}
}
int query(node *root)//匹配
{
int i=0,cnt=0,index,len=strlen(str);
node *p=root;
while(str[i])
{
index=str[i]-'a';
while(p->next[index]==NULL && p!=root)//匹配失败，则用失败指针转移
p=p->fail;
p=p->next[index];
p=(p==NULL)?root:p;
node *temp=p;
while(temp!=root && temp->count!=-1){
cnt+=temp->count;
temp->count=-1;//避免重复计数，标记为-1
temp=temp->fail;
}
i++;
}
return cnt;
}
int main()
{
int n,T;
scanf("%d",&T);
while(T--)
{
node *root=new node();
scanf("%d",&n);
getchar();
while(n--)
{
gets(keyword);
insert(keyword,root);
}
build_ac_automation(root);
scanf("%s",str);
printf("%d\n",query(root));
}
return 0;
}
hdu1277全文检索
View Code
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int kind = 10;
struct node
{
node *fail;//失败指针
node *next[kind];
int count;//单词结尾的标记
node(){//构造函数初始化
fail=NULL;
count=0;
memset(next,NULL,sizeof(next));
}
}*q[500001];//队列，在构造失败指针时用
char keyword[10001][61];//输入的单词
char str[60001];//模式串
int head,tail,num;
bool vis[10001];
void insert(char *str,node *root)//为单词构造trie树，
{
node *p=root;
int i=0,index;
while(str[i])
{
index=str[i]-'0';
if(p->next[index]==NULL)
p->next[index]=new node();
p=p->next[index];
i++;
}
p->count=num;//单词结尾
}
void build_ac_automation(node *root)
{
int i;
head=tail=0;
root->fail=NULL;
q[head++]=root;
while(head!=tail)
{
node *temp=q[tail++];
node *p=NULL;
for(i=0;i<kind;i++)
{
if(temp->next[i]!=NULL)
{
if(temp==root)temp->next[i]->fail=root;
else{
p=temp->fail;
while(p!=NULL)
{
if(p->next[i]!=NULL)
{
temp->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
if(p==NULL) temp->next[i]->fail=root;
}
q[head++]=temp->next[i];
}
}
}
}
int query(node *root)//匹配
{
int i=0,cnt=0,index,len=strlen(str);
node *p=root;
while(str[i])
{
index=str[i]-'0';
while(p->next[index]==NULL && p!=root)//匹配失败，则用失败指针转移
p=p->fail;
p=p->next[index];
p=(p==NULL)?root:p;
node *temp=p;
while(temp!=root && temp->count>0 && !vis[temp->count]){
cnt++;
vis[temp->count]=true;//标记，避免重复计数
temp=temp->fail;
}
i++;
}
return cnt;
}
int main()
{
int n,m;
char strr[10000];
while(scanf("%d %d",&n,&m)==2)
{
scanf("%s",str);
for(int i=1;i<n;i++)
{
scanf("%s",strr);
strcat(str,strr);
}
node *root=new node();
getchar();
for(int i=0;i<m;i++)
{
getchar();
scanf("[Key No. %d] %s",&num,strr);
insert(strr,root);
}
build_ac_automation(root);
memset(vis,false,sizeof(vis));
int count=query(root);
if(count==0)
{
puts("No key can be found !");
continue;
}
printf("Found key:");
for(int i=m;i>=1;i--)
{
if(vis[i])
printf(" [Key No. %d]",i);
}
puts("");
}
return 0;
}
hdu2896 病毒侵袭
跟上题类似，模板题，就是内存开得大了些
View Code
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int kind = 129;
struct node
{
node *fail;//失败指针
node *next[kind];
int count;//单词结尾的标记
node(){//构造函数初始化
fail=NULL;
count=0;
memset(next,NULL,sizeof(next));
}
}*q[500001];//队列，在构造失败指针时用
char keyword[51];//输入的单词
char str[10001];//模式串
int head,tail,num;
bool vis[510];
void insert(char *str,node *root)//为单词构造trie树，
{
node *p=root;
int i=0,index;
while(str[i])
{
index=str[i];
if(p->next[index]==NULL)
p->next[index]=new node();
p=p->next[index];
i++;
}
p->count=num++;//单词结尾
}
void build_ac_automation(node *root)
{
int i;
head=tail=0;
root->fail=NULL;
q[head++]=root;
while(head!=tail)
{
node *temp=q[tail++];
node *p=NULL;
for(i=0;i<kind;i++)
{
if(temp->next[i]!=NULL)
{
if(temp==root)temp->next[i]->fail=root;
else{
p=temp->fail;
while(p!=NULL)
{
if(p->next[i]!=NULL)
{
temp->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
if(p==NULL) temp->next[i]->fail=root;
}
q[head++]=temp->next[i];
}
}
}
}
int query(node *root)//匹配
{
int i=0,cnt=0,index,len=strlen(str);
node *p=root;
while(str[i])
{
index=str[i];
while(p->next[index]==NULL && p!=root)//匹配失败，则用失败指针转移
p=p->fail;
p=p->next[index];
p=(p==NULL)?root:p;
node *temp=p;
while(temp!=root && temp->count>0 && !vis[temp->count]){
cnt++;
vis[temp->count]=true;//标记，避免重复计数
temp=temp->fail;
}
if(cnt>=3)
return cnt;
i++;
}
return cnt;
}
int main()
{
int n,m;
char strr[210];
while(scanf("%d",&n)==1)
{
getchar();
num=1;
node *root=new node();
for(int i=0;i<n;i++)
{
gets(strr);
insert(strr,root);
}
build_ac_automation(root);
scanf("%d",&m);
getchar();
int total=0;
for(int i=1;i<=m;i++)
{
gets(str);
memset(vis,false,sizeof(vis));
int count=query(root);
if(count!=0)
{
total++;
printf("web %d:",i);
for(int j=1;j<=n;j++)
if(vis[j])
printf(" %d",j);
printf("\n");
}
}
printf("total: %d\n",total);
}
return 0;
}
hdu3065 病毒侵袭持续中
还是一样的题
View Code
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int kind = 26;
struct node
{
node *fail;//失败指针
node *next[kind];
int count;//单词结尾的标记
node(){//构造函数初始化
fail=NULL;
count=-1;
memset(next,NULL,sizeof(next));
}
}*q[500001];//队列，在构造失败指针时用
char keyword[1001][51];//输入的单词
char str[2000001];//模式串
int head,tail,num;
int cc[1001];
void insert(char *str,node *root)//为单词构造trie树，
{
node *p=root;
int i=0,index;
while(str[i])
{
index=str[i]-'A';
if(p->next[index]==NULL)
p->next[index]=new node();
p=p->next[index];
i++;
}
p->count=num++;//单词结尾
}
void build_ac_automation(node *root)
{
int i;
head=tail=0;
root->fail=NULL;
q[head++]=root;
while(head!=tail)
{
node *temp=q[tail++];
node *p=NULL;
for(i=0;i<kind;i++)
{
if(temp->next[i]!=NULL)
{
if(temp==root)temp->next[i]->fail=root;
else{
p=temp->fail;
while(p!=NULL)
{
if(p->next[i]!=NULL)
{
temp->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
if(p==NULL) temp->next[i]->fail=root;
}
q[head++]=temp->next[i];
}
}
}
}
void query(node *root)//匹配
{
int i=0,index,len=strlen(str);
node *p=root;
while(str[i])
{
if(!isupper(str[i]))//若非大写字母，则匹配失败，而且之前的匹配信息不可用，需要重新从root开始
{
p=root;
i++;
continue;
}
index=str[i]-'A';
while(p->next[index]==NULL && p!=root)//匹配失败，则用失败指针转移
p=p->fail;
p=p->next[index];
p=(p==NULL)?root:p;
node *temp=p;
while(temp!=root && temp->count!=-1){
cc[temp->count]++;
temp=temp->fail;
}
i++;
}
}
int main()
{
int n;
while(scanf("%d",&n)==1)
{
getchar();
num=0;
node *root=new node();
for(int i=0;i<n;i++)
{
gets(keyword[i]);
insert(keyword[i],root);
}
build_ac_automation(root);
memset(cc,0,sizeof(cc));
int total=0;
gets(str);
query(root);
for(int i=0;i<n;i++)
{
if(cc[i]!=0)
printf("%s: %d\n",keyword[i],cc[i]);
}
}
return 0;
}