P2444

发表于 分类于
[POI2000]病毒

[POI2000]病毒

刚看到的时候确实有些懵。

换到自动机上看一看，玄机在于——环。

自动机上不经过匹配节点并且形成了一个环说明我们可以造出来一个无限长的复合要求的字符串。

然后没了。

时间复杂度 $O(\sum_{i=1}^{n}|t_i|)$。

代码：

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
}using Ehnaev::read;

const ll N=1e6;

ll flg,n,tot;
ll cnt[N+5],trie[N+5][2],nxt[N+5],lst[N+5];
bool vis[N+5];
char buft[N+5];
char *t[N+5],*nowt=buft;

inline void Ins(char *str) {
  ll len=strlen(str),p=0;
  for(ll k=0;k<len;k++) {
    ll ch=str[k]-'0';if(!trie[p][ch]) trie[p][ch]=++tot;p=trie[p][ch];
  }
  cnt[p]=1;
}

inline void AC_Pre() {
  queue<ll> q;
  for(ll c=0;c<2;c++) {
    ll u=trie[0][c];if(u) {nxt[u]=0;lst[u]=0;q.push(u);}
  }
  while(!q.empty()) {
    ll h=q.front();q.pop();
    for(ll c=0;c<2;c++) {
      ll u=trie[h][c];if(!u) {trie[h][c]=trie[nxt[h]][c];continue;}
      q.push(u);ll v=nxt[h];while(v&&!trie[v][c]) v=nxt[v];
      nxt[u]=trie[v][c];lst[u]=cnt[nxt[u]]?nxt[u]:lst[nxt[u]];
    }
  }
}

inline void Dfs(ll p) {
  if(vis[p]) {flg=1;return;}vis[p]=1;
  for(ll i=0;i<2;i++) {
    if(cnt[trie[p][i]]||lst[trie[p][i]]) continue;Dfs(trie[p][i]);
    if(flg) return;
  }
  vis[p]=0;
}

int main() {

  n=read();

  for(ll i=1;i<=n;i++) {
    t[i]=nowt;scanf("%s",t[i]);nowt+=strlen(t[i])+2;
    Ins(t[i]);
  }

  AC_Pre();Dfs(0);

  if(flg) {printf("TAK\n");}
  else {printf("NIE\n");}

  return 0;
}