link:http://acm.hdu.edu.cn/showproblem.php?pid=2222
今天看了一下kmp匹配的时候,正好又一次遇到了这个东东,就顺便看了一下这个,发现真心有难度啊,
不是很理解~~~要搞懂ac自动机的话,先得有trie和kmp模式匹配算法的基础,表示这两项到现在
都不具备。。不过搜了一个模板,算是研究了一下午了,敲了好几遍,还出了好多错误,
后来百度一道纯ac自动机的水题,发现好像那模板就是这题的代码、、、
好囧~~~算是半看半默的敲了一遍把,留着当模板~~下面是我的代码
code:

/*
Ac自动机模板:
insert();建树
build_ac_automation();构造失败指针
query();查询
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
const int kind=26;/*字符种类*/
struct node/*trie树节点结构*/
{
node *fail;/*失败指针*/
node *next[kind];/*trie每个节点的子节点*/
int count;/*以当前节点为单词结尾的个数*/
node()/*构造函数*/
{
fail=NULL;
count=0;
memset(next,NULL,sizeof(next));
}
}*que[1000000];/*队列*/

char key_word[100];/*目的串*/
char str[10000000];/*模式串*/

int front,rear;/*队列的头尾*/

void insert(char *str,node *root)/*把单词加入trie中*/
{
node *p=root;
int i=0;
int index;
while(str[i])/*将每个字母加入到trie树中*/
{
index=str[i]-‘a’;
if(p->next[index]==NULL)
{
p->next[index]=new node();
}
p=p->next[index];
i++;
}
p->count++;/*在单词的最后一个节点count++,代表一个单词*/
}

/*设这个节点上的字母为c,沿着它的父亲的失败指针走,直到走到一个节点,
它的儿子中也有字母为c的节点。然后把当前节点的失败指针指向那个字母也是
c的儿子。如果一直走到了root都没找到,那就把失败指针指向root*/
void build_ac_automation(node *root)/*构造失败指针*/
{
int i;
root->fail=NULL;
que[rear++]=root;
while(front<rear)/*队列*/
{
node *temp=que[front];
node *p=NULL;
for(i=0;i<26;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;
}
que[rear++]=temp->next[i];
}
}
front++;
}
}

/*根据具体题目,重写查询方法*/
int query(node *root,char *str)
{
int i=0,cnt=0;
int index;
node *p=root;
while(str[i])
{
index=str[i]-‘a’;
while(p->next[index]==NULL&&p!=root)
p=p->fail;
p=p->next[index];
if(p==NULL)
p=root;
node *temp=p;
while(temp!=root&&temp->count!=-1)
{
cnt+=temp->count;
temp->count=-1;
temp=temp->fail;
}
i++;
}
return cnt;
}

int main()
{
int t;
scanf(“%d”,&t);
while(t–)
{
int n;
scanf(“%d”,&n);
node *root=new node;
while(n–)
{
scanf(“%s”,key_word);
insert(key_word,root);
}
build_ac_automation(root);
scanf(“%s”,str);
printf(“%d\n”,query(root,str));
}
return 0;
}

 

介绍一个blog,对这个讲述的蛮好~http://www.cppblog.com/mythit/archive/2009/04/21/80633.html

发表评论

电子邮件地址不会被公开。

Post Navigation