BZOJ 2938 病毒

发表于 | 更新于

Link

Solution

建立AC自动机，条件等价于沿着非单词节点走出一个环。这是比较显然的：走到了一个曾经到过的节点，就说明两次经过这个节点之间的字符串循环起来就符合题意了。

Tips

又被自己乱想的不存在的边界情况卡住了。以后如果对自己的想法有什么异议，一定要造出具体到数据的反例。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=30000+10;
namespace AC
{
	const int SIZE=MAXN;
	struct Node
	{
		Node *son[2],*fail,*last;
		int cnt;
		Node(){cnt=0;son[0]=son[1]=fail=last=0;}
		Node *&next(char c){return son[c-'0'];}
		int num();
	}*ME=(Node*)malloc(SIZE*sizeof(Node)),*POOL=ME,*root=new Node;
	Node *newNode() {return new(ME++) Node;}
	int Node::num(){return this-POOL+1;}
	void Insert(char *s)
	{
		Node *cur=root;
		for(int i=1,L=strlen(s+1);i<=L;i++)
		{
			if(!cur->next(s[i])) cur->next(s[i])=newNode();
			cur=cur->next(s[i]);
		}
		cur->cnt++;
	}
	void Build()
	{
		static Node *Q[SIZE];int he=1,ta=0;
		root->fail=root;root->last=0;
		for(char c='0';c<='1';++c)
			if(!root->next(c)) root->next(c)=root;
			else
			{
				root->next(c)->fail=root;
				root->next(c)->last=0;
				Q[++ta]=root->next(c);////root;
			}
		while(he<=ta)
		{
			Node *cur=Q[he++];
			for(char c='0';c<='1';++c)
			{
				Node *&son=cur->next(c);
				if(!son) son=cur->fail->next(c);
				else
				{
					son->fail=cur->fail->next(c);
					son->last=son->fail->cnt?son->fail:son->fail->last;
					Q[++ta]=son;
				}
			}
		}
	}
}
using namespace AC;
struct Edge{int to,pre;}e[SIZE<<2];int id[SIZE],ec;
void Adde(int f,int t){e[++ec].to=t;e[ec].pre=id[f];id[f]=ec;}
bool DAG()
{
	static int Q[SIZE],he,ta,deg[SIZE];
	int n=ME-POOL;he=1,ta=0;
	for(Node *ptr=POOL;ptr!=ME;++ptr)
		for(char c='0';c<='1';++c)
			if(!ptr->next(c)->cnt && !ptr->next(c)->last)
			{
				Adde(ptr->num(),ptr->next(c)->num());
				deg[ptr->next(c)->num()]++;
			}
	for(int i=1;i<=n;i++)
		if(!deg[i]) Q[++ta]=i;
	while(he<=ta)
	{
		int cur=Q[he++];
		for(int i=id[cur];i;i=e[i].pre)
		{
			int u=e[i].to;
			deg[u]--;
			if(!deg[u])
				Q[++ta]=u;
		}
	}
	return ta==n;
}
int main()
{
	freopen("input","r",stdin);
	static char s[MAXN];
	int n;get(n);
	for(int i=1;i<=n;i++)
		scanf("%s",s+1),Insert(s);
	Build();
	puts(DAG()?"NIE":"TAK");
	return 0;
}
/* AC Record(Bugs) *
 * WA ptr->next(c)->last 
 * * * * * * * * * */