记录编号	169605	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[POI 2000]病毒	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.030 s
提交时间	2015-07-09 21:11:22	内存使用	0.86 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <map>
#include <string>
#include <queue>
#include <stack>
using namespace std;
typedef long long LL;
///===================struct declaration======================

///===================var declaration=========================
const int MAXN=30010;
int n, Node_cnt = 1;
int fail[MAXN], next[MAXN][2], Ind[MAXN];
bool is_end[MAXN], vis[MAXN], ins[MAXN];
queue <int> Q;
///===================function declaration====================
void Insert(char *ch);
void GetFail();
bool dfs(int x);
///===================main code===============================
int main(){
#ifndef ONLINE_JUDGE
	 freopen("wir.in","r",stdin);
	 freopen("wir.out","w",stdout);
#endif
	 scanf("%d", &n);
	 memset(next, -1, sizeof(next));
	 for(int i = 1; i <= n; i ++){
		 char ch[MAXN]; scanf("%s", ch);
		 Insert(ch);
	 }
	 GetFail();
	 if (dfs(1))
		 printf("TAK\n");
	 else
		 printf("NIE\n");
	 return 0;
}
///==================function code===========================
void Insert(char *ch){
	int p = 1;
	for(int i = 0; ch[i]; i ++){
		if (next[p][ch[i] - '0'] == -1)
			next[p][ch[i] - '0'] = ++ Node_cnt;
		p = next[p][ch[i] - '0'];
	}
	is_end[p] = true;
}
void GetFail(){
	for(int i = 0; i < 2; i ++)
		if (next[1][i] == -1)
			next[1][i] = 1;
		else{
			Q.push(next[1][i]);
			fail[next[1][i]] = 1;
		}
	while (!Q.empty()){
		int x = Q.front(); Q.pop();
		int temp = x;
		while (temp != 1){
			if (is_end[temp]){
				is_end[x] = true;
				break;
			}
			else
				temp = fail[temp];
		}
		for(int i = 0; i < 2; i ++){
			if (next[x][i] == -1)
				next[x][i] = next[fail[x]][i];
			else{
				fail[next[x][i]] = next[fail[x]][i];
				Q.push(next[x][i]);
			}
			Ind[next[x][i]] ++;
		}
	}
}
bool dfs(int x){
	ins[x] = true;
	for(int i = 0; i < 2; i ++){
		if (ins[next[x][i]])
			return true;
		if (vis[next[x][i]] || is_end[next[x][i]]) continue;
		vis[next[x][i]] = true;
		if (dfs(next[x][i]))
			return true;
	}
	ins[x] = false;
	return false;
}