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
| #define REP(i, s, e) for (int i = s; i <= e; i++) #define DREP(i, s, e) for (int i = s; i >= e; i--) #define DEBUG fprintf(stderr, "Passing [%s] in Line %d\n", __FUNCTION__, __LINE__)
#define chkmax(a, b) a = max(a, b) #define chkmin(a, b) a = min(a, b)
#include <iostream> #include <cstring> #include <cstdio>
using namespace std; const int maxn = 2000 + 10, maxlen = 30000 + 10, sumS = maxlen;
int ch[sumS][3], fail[sumS], rt, cur; bool End[sumS]; void insert(char s[]) { int now = rt; for (int i = 1; s[i]; i++) now = !ch[now][s[i]] ? ch[now][s[i]] = ++cur : ch[now][s[i]]; End[now] = 1; } int q[sumS], head, tail; void build() { head = 1; REP(i, 1, 2) if (ch[0][i]) q[++tail] = ch[0][i]; while (head <= tail) { int x = q[head++]; if (End[fail[x]]) End[x] = 1; REP(i, 1, 2) if (ch[x][i]) fail[q[++tail] = ch[x][i]] = ch[fail[x]][i]; else ch[x][i] = ch[fail[x]][i]; } }
bool vis[sumS], ins[sumS]; void dfs(int x = rt) { if (ins[x]) {puts("TAK");exit(0);} if (vis[x] || End[x]) return; vis[x] = ins[x] = 1; REP(i, 1, 2) if (ch[x][i]) dfs(ch[x][i]); ins[x] = 0; }
int n; char s[maxlen];
int main() { #ifdef CraZYali freopen("2444.in", "r", stdin); freopen("2444.out", "w", stdout); #endif cin >> n; while (n--) { scanf("%s", s + 1); for (int i = 1; s[i]; i++) s[i] -= '0'-1; insert(s); } build(); #ifdef CraZYali REP(i, 1, cur) printf("%d%c", (int)fail[i], i == cur ? '\n' : ' '); REP(i, 1, cur) printf("%d%c", (int)End[i], i == cur ? '\n' : ' '); #endif dfs(); puts("NIE"); return 0; }
|