题目描述
输入
输出
样例输入
3
01
11
00000
样例输出
NIE
题解
AC自动机
如果一个串能无限长，那么说明它可以一直匹配，而始终不匹配病毒串。
每次查找到下一个字符时，只有两种可能：
(1)存在子节点，进入该子节点。
(2)不存在子节点，进入fail节点，直至存在子节点。
那么是否能无限匹配，就转化为有没有相应的环。
这里为了方便，将fail合并到子节点。
除了排除病毒串节点以外，还应排除fail指向病毒串的节点，因为该串后缀为病毒串前缀。
然后dfs判环即可。
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 using namespace std; 5 queue<int> q; 6 int nt[30001][2] , fail[30001] , cnt[30001] , tot = 1; 7 char str[30001]; 8 bool vis[30001] , ins[30001] , flag; 9 int deep[30001] , low[30001] , sta[30001] , ind , h; 10 void build() 11 { 12 int u , t , i; 13 q.push(1); 14 nt[0][0] = nt[0][1] = 1; 15 while(!q.empty()) 16 { 17 u = q.front(); 18 q.pop(); 19 for(i = 0 ; i < 2 ; i ++ ) 20 { 21 if(nt[u][i]) 22 { 23 q.push(nt[u][i]); 24 t = fail[u]; 25 while(t && !nt[t][i]) 26 t = fail[t]; 27 fail[nt[u][i]] = nt[t][i]; 28 cnt[nt[u][i]] |= cnt[nt[t][i]]; 29 } 30 else 31 nt[u][i] = nt[fail[u]][i]; 32 } 33 } 34 } 35 bool dfs(int x) 36 { 37 ins[x] = vis[x] = 1; 38 int i , y; 39 for(i = 0 ; i < 2 ; i ++ ) 40 { 41 y = nt[x][i]; 42 if(ins[y] || (!vis[y] && !cnt[y] && dfs(y))) 43 return 1; 44 } 45 ins[x] = 0; 46 return 0; 47 } 48 int main() 49 { 50 int n , i , t , l; 51 scanf("%d" , &n); 52 while(n -- ) 53 { 54 scanf("%s" , str); 55 l = strlen(str); 56 t = 1; 57 for(i = 0 ; i < l ; i ++ ) 58 { 59 if(!nt[t][str[i] - ‘0‘]) 60 nt[t][str[i] - ‘0‘] = ++tot; 61 t = nt[t][str[i] - ‘0‘]; 62 } 63 cnt[t] = 1; 64 } 65 build(); 66 printf("%s\n" , dfs(1) ? "TAK" : "NIE"); 67 return 0; 68 }
原文：http://www.cnblogs.com/GXZlegend/p/6265366.html