先把所有串建一个AC自动机，
如果要找一个不包含任意一个串的串，
说明这个串一直在AC自动机上匹配但匹配不到，
也就是说，匹配时除去val值为1的点，除去fail指针指向val值为1的点，是否有环，dfs即可。
因为val值为1说明匹配上，fail指针指向的点x，根到x所形成的字符串是当前串的后缀，
所以也得除去fail指针指向val值为1的点的点。
——代码
1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 7 const int MAXN = 30001; 8 int n, cnt; 9 int ch[MAXN << 2][2], fail[MAXN << 2]; 10 char s[MAXN]; 11 bool vis[MAXN << 2], ins[MAXN << 2], val[MAXN << 2]; 12 queue <int> q; 13 14 inline void insert() 15 { 16 int i, x, len = strlen(s), now = 0; 17 for(i = 0; i < len; i++) 18 { 19 x = s[i] - '0'; 20 if(!ch[now][x]) ch[now][x] = ++cnt; 21 now = ch[now][x]; 22 } 23 val[now] = 1; 24 } 25 26 inline void make_fail() 27 { 28 int i, x, now; 29 for(i = 0; i <= 1; i++) if(ch[0][i]) q.push(ch[0][i]); 30 while(!q.empty()) 31 { 32 now = q.front(), q.pop(); 33 for(i = 0; i <= 1; i++) 34 { 35 if(!ch[now][i]) 36 { 37 ch[now][i] = ch[fail[now]][i]; 38 continue; 39 } 40 fail[ch[now][i]] = ch[fail[now]][i]; 41 q.push(ch[now][i]); 42 val[ch[now][i]] |= val[fail[ch[now][i]]]; 43 } 44 } 45 } 46 47 inline bool dfs(int u) 48 { 49 int i, v; 50 ins[u] = 1; 51 for(i = 0; i <= 1; i++) 52 { 53 v = ch[u][i]; 54 if(ins[v]) return 1; 55 if(val[v] || vis[v]) continue; 56 vis[v] = 1; 57 if(dfs(v)) return 1; 58 } 59 ins[u] = 0; 60 return 0; 61 } 62 63 int main() 64 { 65 int i, j; 66 scanf("%d", &n); 67 for(i = 1; i <= n; i++) 68 { 69 scanf("%s", s); 70 insert(); 71 } 72 make_fail(); 73 if(dfs(0)) puts("TAK"); 74 else puts("NIE"); 75 return 0; 76 }