记录编号	371534	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[POI 2000]病毒	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.052 s
提交时间	2017-02-16 11:39:51	内存使用	0.89 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=30010;
void insert(const char*,int);
void getfail();
bool dfs(int);
int ch[maxn][2]={{0}},val[maxn]={0},f[maxn]={0},last[maxn]={0},cnt=0,q[maxn];
bool vis[maxn]={false},ins[maxn]={false};
char s[maxn];
int n;
int main(){
	freopen("wir.in","r",stdin);
	freopen("wir.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%s",s);
		insert(s,i);
	}
	getfail();
	printf(dfs(0)?"TAK\n":"NIE\n");
	return 0;
}
void insert(const char *c,int id){
	int x=0;
	while(*c){
		if(!ch[x][*c-'0'])ch[x][*c-48]=++cnt;
		x=ch[x][*c++-'0'];
	}
	val[x]=id;
}
void getfail(){
	int x,y,head=0,tail=0;
	for(int c=0;c<2;c++)if(ch[0][c])q[tail++]=ch[0][c];
	while(head!=tail){
		x=q[head++];
		for(int c=0;c<2;c++){
			if(ch[x][c]){
				if(val[ch[x][c]]||last[ch[x][c]])continue;
				y=f[x];
				while(y&&!ch[y][c])y=f[y];
				f[ch[x][c]]=ch[y][c];
				last[ch[x][c]]=val[f[ch[x][c]]]?f[ch[x][c]]:last[f[ch[x][c]]];
				q[tail++]=ch[x][c];
			}
			else ch[x][c]=ch[f[x]][c];
		}
	}
}
bool dfs(int x){
	if(val[x]||last[x])return false;
	if(ins[x])return true;
	if(vis[x])return false;
	vis[x]=true;
	ins[x]=true;
	for(int c=0;c<2;c++)if(dfs(ch[x][c]))return true;
	ins[x]=false;
	return false;
}