bzoj 2938 AC自动机

根据题意建出trie图，代表单词的点不能走，直接或间接指向它的点也不能走。这样的话如果能在图中找到一个环的话就是TAK，否则是NIE。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #define N 30005

 using namespace std;

 int n;bool flag;

 int ch[N][];

 bool yes[N][];

 char s[N];int cnt;

 bool ok[N];

 void inn()

 {

     int now=;

     int l=strlen(s);

     for(int i=;i<l;i++)

     {

         if(!ch[now][s[i]-''])ch[now][s[i]-'']=++cnt,yes[now][s[i]-'']=;

         now=ch[now][s[i]-''];

     }

     ok[now]=;

 }

 int f[N];

 int vis[N],in[N];

 queue<int>q;

 void dfs(int x)

 {

 //    cout<<x<<endl;

 //    cout<<in[1]<<"SS"<<endl;

     vis[x]=;in[x]=;

     for(int i=;i<;i++)

     {

         if(!vis[ch[x][i]])

         {

             if(!ok[ch[x][i]])

             {

                 dfs(ch[x][i]);

             }

         }

         else if(in[ch[x][i]])

         {

             flag=;

         }

     }

     in[x]=;

 }

 bool fail()

 {

     for(int i=;i<;i++)if(ch[][i])q.push(ch[][i]);

     while(!q.empty())

     {

         int tmp=q.front();q.pop();

         for(int i=;i<;i++)

         {

             int u=ch[tmp][i];

             if(!u)

             {

                 ch[tmp][i]=ch[f[tmp]][i];continue;

             }

             f[u]=ch[f[tmp]][i];

             if(ok[f[u]])ok[u]=;

             q.push(u);

         }

     }

     dfs();

     if(flag)return ;

     return ;

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++)

     {

         scanf("%s",s);inn();

     }

     //cout<<f[5]<<endl;

     if(fail())puts("TAK");

     else puts("NIE");

     return ;

 }