洛谷题目传送门

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;

}