洛谷P2444 [POI2000]病毒(AC自动机,DFS求环)

洛谷题目传送门

AC自动机入门——yyb巨佬的博客

AC自动机入手经典好题(虽然年代久远)

有了fail指针,trie树就不是原来的树型结构了,我们可以把它叫做trie图,由父节点向子节点连的边和fail代表的边构成(都是单向边)。

最模板的AC自动机,就是直接匹配字符串。然而这题思维并非如此简单。

来一波逆向思维。假设我们构造出了一个无限长的安全代码,再拿到AC自动机上匹配,会发生什么?

没错,当我们一位一位地匹配的时候,我们会发现,永远都不会跳到某个病毒代码段结尾的位置(以后把这里称作危险节点,因为匹配到此处表明已经出现了某个病毒代码段),然后似乎会在自动机里永无止境地打转转。。。。。。

既然这个自动机又像一个图,那我们的问题不就变成了——在AC自动机(trie图)中寻找一个环,并且环上没有任何危险节点,并且还要注意,这个环能被根节点访问到(也就是说从根节点出发能在不经过危险节点的情况下走到到这个环,不然在模拟AC自动机匹配的时候无法到达这个这个环,也就失去了意义,楼上Dalao这里可能表述不尽准确)。

找环就属于图论了,DFS一遍,只不过必须从根节点出发(上面提到)。开两个布尔数组,一个记录历史是否访问过,一个记录是否在搜索的栈中。如果搜索过程中发现将要访问的下一个节点之间已经入栈了,就找到解了。不走危险节点,不走历史访问过而已经不在栈中的节点。还注意一下,如果某节点fail指向的是危险节点,那么该节点也是危险节点,AC自动机的性质,这里不再赘述。

多说几句,数据太小(因为年代久远?),根本不像AC自动机的题目。。。。。。提交记录都是0ms,若想冲榜要压空间,开short吧。我还是承认yyb_test比FlashHu强多啦!

下面是数组代码,可结合注释与上面的分析。

#include<cstdio>
#include<cstdlib>
const int N=33333;
short c[N][2],f[N],q[N];//没错short
bool e[N],vis[N],inst[N];
char s[N];
void dfs(short u)
{
if(inst[u])puts("TAK"),exit(0);//找到啦,直接拜拜
if(vis[u]||e[u])return;//走不通
inst[u]=vis[u]=1;
dfs(c[u][0]);
dfs(c[u][1]);
inst[u]=0;//两个标记意义不同,这个记得搜完清0
}
int main()
{
fread(s,1,N,stdin);
short n,i,u,v,cnt=0,h=0,t=0;
char*p=s;
n=*p&15;
while(*++p>' ')n*=10,n+=*p&15;
//建自动机
while(n--)
{
while(*++p<=' ');
for(u=0;*p>' ';++p)
{
if(!c[u][i=*p&1])c[u][i]=++cnt;
u=c[u][i];
}
e[u]=1;//标记危险节点(这时还没把所有的危险节点都找出来)
}
//处理fail以及危险节点
if(c[0][0])q[++t]=c[0][0];
if(c[0][1])q[++t]=c[0][1];
while(h<t)
{
u=q[++h];
for(i=0;i<=1;++i)
if((v=c[u][i]))f[q[++t]=v]=c[f[u]][i],e[v]|=e[f[v]];
//这时候才都找出来了
else c[u][i]=c[f[u]][i];//直接改空儿子,方便失配处理
}
dfs(0);
puts("NIE");//这时全搜遍了还没找到
return 0;
}
上一篇:Js 面向对象之封装,继承,原型,原型链


下一篇:【js】版本号对比处理方案