题解 P2444 【[POI2000]病毒】

AC自动机入门——[yyb巨佬的博客](http://www.cnblogs.com/cjyyb/p/7196308.html) 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; } ```