HDU2896病毒侵袭(ac自动机)

时间:2022-08-27 06:21:53
网上很多代码都略显繁琐,看了一下yy dalao的代码感觉很好,但他懒得打题解(好吧我也是 以0为根节点的话,我把yy的一段代码删了改用fail[c]=x==0?0:ch[fail[x]][i];来实现特判,效果还不错! 也算是AC自动机的模版题吧,用了一个id数组来储藏每一个特征码的最后一个字符所在位置,再用vis来看网站源码中有哪条特征码(即哪条特征码的id被访问到 HDU2896病毒侵袭(ac自动机)HDU2896病毒侵袭(ac自动机)
#include<cstdio>
#include
<cstring>
using namespace std;
char s[205],t[10005];
int fail[100001],q[100002],ch[100002][130],val[100002],id[505],vis[100002];
int sz=0,ans=0,n;
void trie(int x)
{
int u=0,m=strlen(s);
for(int i=0;i<m;i++)
{
int c=s[i];
if(!ch[u][c])
ch[u][c]
=++sz;
u
=ch[u][c];
}
id[x]
=u;
val[u]
++;
}
void makefail()
{
int head=0,tail=1;
q[
1]=0;fail[0]=0;
while(head!=tail)
{
int x=q[++head];if(head>=100000)head=0;
for(int i=0;i<128;i++){
int c=ch[x][i];
if(!c){ch[x][i]=ch[fail[x]][i];continue;}
q[
++tail]=c;if(tail>=100000)tail=0;
fail[c]
=x==0?0:ch[fail[x]][i];
}
}
}
void ac(int x)
{
int f=0,k=0,len=strlen(t);
memset(vis,
0,sizeof(vis));
for(int i=0;i<len;i++){
int u=t[i];
k
=ch[k][u];
for(int j=k;j;j=fail[j]){if(val[j]){f=1;vis[j]=1;}}
}
if(!f)return;
ans
++;printf("web %d:",x);
for(int i=1;i<=n;i++)
if(vis[id[i]])printf(" %d",i);
printf(
"\n");
}
int main()
{
int m;
scanf(
"%d",&n);
for(int i=1;i<=n;i++){
scanf(
"%s",s);
trie(i);
}
makefail();
scanf(
"%d",&m);
for(int i=1;i<=m;i++)
{
scanf(
"%s",t);
ac(i);
}
printf(
"total: %d\n",ans);
return 0;
}
View Code