题目类型:AC自动机
传送门:>Here<
题意:给出(N)个(01)字符串,称为病毒串。问是否存在一个无限长的(01)串(T),使得其中不包含任何一个病毒串
解题思路
如果我们拿(T)串去进行匹配会发生什么?
考虑(AC)自动机匹配的条件:匹配时能够到达一个单词的结尾。因此找到(T)串的条件就是(T)串在匹配时永远不会到达一个单词的结尾,而是不停的能够在那些非结尾的点上绕圈
因此我们先构建(Trie)树和(Fail)指针,然后在(AC)自动机上找环。
特别注意(AC)自动机是有向图,所以不能简简单单的(DFS)看看有没有重复访问的。有关图的(DFS)问题无论如何,一定要先想到(DFS)树。在无向图中,一条边不是树边就是后向边,而后向边也就是有一端已经访问过了。所以只需要简单的判断是否访问即可。而由于有向图是单向边,所以还会存在横叉边和前向边。但横叉边和前向边都不可能形成环,因此我们的任务还是寻找后向边。后向边的找法很简单,可以维护一个栈,栈内保留从当前节点一直到(DFS)树根的所有节点,如果这条边所到达的点在栈内也就找到了后向边。
另外我们在(DFS)的过程中不能走那些不能碰到的点,例如结尾节点。不妨称之为危险节点。
危险节点真的只是结尾节点吗?我们之前在做(AC)自动机的时候,如果发现一个能匹配的结尾节点,还需要沿着(Fail)走统计后缀。例如两个字符串(S_1=101)和(S_2=1010).两个串的结尾肯定都是危险节点,但是我们发现(S_1)是(S_2)的前缀,如果(S_2)能够匹配(S_1)一定也能够匹配。因此(S_2)中的倒数第二个字符(1)也是危险节点!这个点也是不能走的!考虑前后缀的特性,我们能够得出结论:如果(u)是结尾节点,则(fail[u])就是危险节点
Code
/*By DennyQi 2018.8.21*/
#include <cstdio>
#include <queue>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define r read()
#define Max(a,b) (((a)>(b)) ? (a) : (b))
#define Min(a,b) (((a)<(b)) ? (a) : (b))
using namespace std;
typedef long long ll;
const int MAXN = 10010;
const int MAXM = 27010;
const int INF = 1061109567;
inline int read(){
int x = 0; int w = 1; register int c = getchar();
while(c ^ '-' && (c < '0' || c > '9')) c = getchar();
if(c == '-') w = -1, c = getchar();
while(c >= '0' && c <= '9') x = (x<<3) + (x<<1) + c - '0', c = getchar(); return x * w;
}
int N;
char s[30010];
int vis[30010],insta[30010];
struct AC_automaton{
int cnt;
int ch[30010][2],fail[30010],last[30010];
queue <int> q;
inline void insert(){
int len = strlen(s), u(0), c;
for(int i = 0; i < len; ++i){
c = s[i] - '0';
if(!ch[u][c]) ch[u][c] = ++cnt;
u = ch[u][c];
}
last[u] = 1;
}
inline void getFail(){
for(int i = 0; i < 2; ++i){
if(ch[0][i]) q.push(ch[0][i]);
}
int u(0);
while(!q.empty()){
u = q.front(); q.pop();
for(int i = 0; i < 2; ++i){
if(ch[u][i]){
fail[ch[u][i]] = ch[fail[u]][i];
if(last[fail[ch[u][i]]]){
last[ch[u][i]] = 1;
}
q.push(ch[u][i]);
}
else{
ch[u][i] = ch[fail[u]][i];
}
}
}
}
void DFS(int u){
if(insta[u]){
printf("TAK");
exit(0);
}
if(last[u]) return;
if(vis[u]) return;
insta[u] = 1;
vis[u] = 1;
for(int i = 0; i < 2; ++i){
DFS(ch[u][i]);
}
insta[u] = 0;
}
}qxz;
int main(){
scanf("%d", &N);
for(int i = 1; i <= N; ++i){
scanf("%s", s);
qxz.insert();
}
qxz.getFail();
qxz.DFS(0);
printf("NIE");
return 0;
}