BZOJ 2938 [POI2000]病毒 (剪枝/A*迭代搜索)

题目大意：给你一些模式串，问是否存在一个无限长的文本串，不包含任何一个给定的模式串

并没有想到去模拟合法的文本串在模式串的Trie图上匹配的过程..我好菜啊

如果一个字符串合法，那么它的每个子串都不是任何一个模式串的结尾，即沿着Fail链跳到根的每个点都不是结尾

一个合法文本串在模式串构成的Trie图上匹配的过程中，会不断沿着一个环去跳

如果一个环合法，那么这个环需要满足环上每个点，以及根节点到第一个接触到环的路径上的每个点，都合法

找合法环的过程中，可以用类似于tarjan边双的方法，用两个数组记录那些点被访问过，以及那些点在栈中

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define NN 30010

 #define ll long long

 #define uint unsigned int

 #define ull unsigned long long

 #define inf 0x3f3f3f3f

 #define idx(x) (x-'0')

 using namespace std;

 int n;

 char str[NN];

 int head[NN],nt[NN],vis[NN],use[NN],cte;

 struct Edge{int to,nxt;}edge[NN*];

 void ae(int u,int v){

     cte++;edge[cte].nxt=head[u];

     edge[cte].to=v,head[u]=cte;

 }

 struct AC{

 int fail[NN],g[NN],ch[NN][],ed[NN],tot;

 void Build_Trie(char *a,int len)

 {

     int x=;

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

         if(!ch[x][idx(a[i])])

             ch[x][idx(a[i])]=++tot;

         x=ch[x][idx(a[i])];

     }ed[x]=;

 }

 void Build_Fail()

 {

     queue<int>q;

     if(ch[][]) q.push(ch[][]);

     if(ch[][]) q.push(ch[][]);

     while(!q.empty())

     {

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

         ae(fail[x],x);

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

             if(ch[x][i]){

                 fail[ch[x][i]]=ch[fail[x]][i];

                 q.push(ch[x][i]);

             }else{

                 ch[x][i]=ch[fail[x]][i];

             }

         }

     }

     q.push();

     while(!q.empty())

     {

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

         for(int j=head[x];j;j=edge[j].nxt){

             int v=edge[j].to;

             if(ed[v]||g[x]) g[v]=;

             q.push(v);

         }

     }

 }

 int find_cir(int x)

 {

     if(vis[x]) return ;

     vis[x]=,use[x]=;

     int ans=;

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

         if(use[ch[x][i]]) return ;

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

             ans=find_cir(ch[x][i]);

         if(ans) return ;

     }use[x]=;return ;

 }

 void solve()

 {

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

         scanf("%s",str+);

         int len=strlen(str+);

         Build_Trie(str,len);

     }Build_Fail();

     int ans=;

     ans=find_cir(ch[][]);

     if(ans){printf("TAK\n");return;}

     memset(vis,,sizeof(vis));

     ans=find_cir(ch[][]);

     if(ans){printf("TAK\n");return;}

     printf("NIE\n");

 }

 }ac;

 int main()

 {

     //freopen("t2.in","r",stdin);

     scanf("%d",&n);

     ac.solve();

     return ;

 }

巴特西

BZOJ 2938 [POI2000]病毒 (剪枝/A*迭代搜索)

最新文章

热门文章