HDUnbsp;2222nbsp;nbsp;Keywordsnbsp;Search（AC自…

本文主要是介绍HDUnbsp;2222nbsp;nbsp;Keywordsnbsp;Search（AC自…，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2222

分析见大牛：http://www.cppblog.com/mythit/archive/2009/07/30/80633.html

模版见大神：http://archive.cnblogs.com/a/2206679/

这个模版貌似废话比较多，其实可以更简略的~ ~ ~

附上自己的代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 500008

typedef struct point{
int count;
struct point *next[26],*fail;
}*Tree,Node;
Tree root;

char str[1000008];
Tree Q[500008];

Tree NEW()
{
int i;
Tree p;
p=(Tree)malloc(sizeof(Node));
for(i=0;i<26;i++)
p->next[i]=NULL;
p->count=0;
p->fail=NULL;
return p;
}

void Build(char ss[])
{
int i=0;
Tree p,s;
p=root;
while(ss[i])
{
if(p->next[ss[i]-'a']==NULL)
{
s=NEW();
p->next[ss[i]-'a']=s;
p=s;
}
else p=p->next[ss[i]-'a'];
i++;
}
p->count++;
}

void AC_Automation()
{
int i,front,rear;
Tree temp,p;
front=rear=0;
Q[front++]=root;
while(rear<front)
{
temp=Q[rear];
rear++;
for(i=0;i<26;i++)
{
if(temp->next[i]==NULL)continue;
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[front++]=temp->next[i];
}
}
}

int search()
{
int i=0,sum=0;
Tree p=root,temp;
while(str[i])
{
while(p->next[str[i]-'a']==NULL && p!=root)
p=p->fail;
p=p->next[str[i]-'a'];
if(p==NULL)
p=root;
temp=p;
while(temp!=root && temp->count!=-1)
{
sum+=temp->count;
temp->count=-1;
temp=temp->fail;
}
i++;
}
return sum;
}

int main()
{
int n,i,ans;
char trie[55];
scanf("%d",&ans);
while(ans--)
{
root=NEW();
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s",trie);
Build(trie);
}
AC_Automation();
scanf("%s",str);
printf("%d\n",search());
}
return 0;
}