BZOJ2938[Poi2000]病毒——AC自动机

  1 #include<cmath>
  2 #include<queue>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<cstdlib>
  6 #include<iostream>
  7 #include<algorithm>
  8 using namespace std;
  9 struct tree
 10 {
 11     int fail;
 12     int vis[3];
 13     bool end;
 14 }a[30001];
 15 int cnt;
 16 int n;
 17 int num;
 18 char s[30001];
 19 bool f[30001];
 20 bool v[30001];
 21 void build(char *s)
 22 {
 23     int l=strlen(s);
 24     int now=0;
 25     for(int i=0;i<l;i++)
 26     {
 27         int x=(s[i]-‘0‘);
 28         if(a[now].vis[x]==0)
 29         {
 30             a[now].vis[x]=++cnt;
 31         }
 32         now=a[now].vis[x];
 33     }
 34     a[now].end=true;
 35 }
 36 void bfs()
 37 {
 38     queue<int>q;
 39     for(int i=0;i<2;i++)
 40     {
 41         if(a[0].vis[i]!=0)
 42         {
 43             a[a[0].vis[i]].fail=0;
 44             q.push(a[0].vis[i]);
 45         }
 46     }
 47     while(!q.empty())
 48     {
 49         int now=q.front();
 50         q.pop();
 51         for(int i=0;i<2;i++)
 52         {
 53             if(a[now].vis[i]!=0)
 54             {
 55                 a[a[now].vis[i]].fail=a[a[now].fail].vis[i];
 56                 q.push(a[now].vis[i]);
 57                 if(a[a[a[now].fail].vis[i]].end)
 58                 {
 59                     a[a[now].vis[i]].end=true;
 60                 }
 61             }
 62             else
 63             {
 64                 a[now].vis[i]=a[a[now].fail].vis[i];
 65             }
 66         }
 67     }
 68 }
 69 void dfs(int d)
 70 {
 71     v[d]=true;
 72     for(int i=0;i<2;i++)
 73     {
 74         if(v[a[d].vis[i]])
 75         {
 76             printf("TAK");
 77             exit(0);
 78         }
 79         else if(!a[a[d].vis[i]].end&&!f[a[d].vis[i]])
 80         {
 81             f[a[d].vis[i]]=true;
 82             dfs(a[d].vis[i]);
 83         }
 84     }
 85     v[d]=false;
 86 }
 87 int main()
 88 {
 89     scanf("%d",&n);
 90     for(int i=1;i<=n;i++)
 91     {
 92         scanf("%s",&s);
 93         build(s);
 94     }
 95     a[0].fail=0;
 96     bfs();
 97     dfs(0);
 98     printf("NIE");
 99     return 0;
100 }