【bzoj2938】[Poi2000]病毒

2015.06.13 16:08 Sat | 6次阅读 | 旧日oi | 固定链接 | 源码

题目大意

给定一些01串,求是否有一个无限长的01串不包含给定的所有串。字符总数不超过30000

题解

把给出的01串建成Trie图,合并fail节点,然后dfs,如果能找到环,就说明存在,否则不存在。
从这道题开始正式转成Trie图了。当模板多敲两遍。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define N 30005
int n,cnt;
char s[N];
int son[N][2],fail[N],mark[N];
void Init()
{
    cnt=1;son[0][0]=son[0][1]=1;
}
void insert()
{
    scanf("%s",s);
    int len=strlen(s),x=1;
    for(int i=0;i<len;i++)
    {
        if(!son[x][s[i]-'0']) son[x][s[i]-'0']=++cnt;
        x=son[x][s[i]-'0'];
    }
    mark[x]=1;
}
queue<int> q;
void build()
{
    q.push(1);fail[0]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int k,v,i=0;i<2;i++)
        {
            if(k=son[u][i])
            {
                for(v=fail[u];v&&!son[v][i];v=fail[v]);
                fail[k]=v=son[v][i];
                mark[k]|=mark[v];
                q.push(k);
            }
            else son[u][i]=son[fail[u]][i];
        }
    }
}
bool vis[N],ins[N];
bool dfs(int u)
{
    ins[u]=1;vis[u]=1;
    for(int v,i=0;i<2;i++) 
    {
        if(ins[v=son[u][i]]) return 1;
        if(vis[v]||mark[v]) continue;
        if(dfs(v)) return 1;
    }
    ins[u]=0;
    return 0;
}
int main()
{
    cin>>n;
    Init();
    for(int i=1;i<=n;i++) insert();
    build();
    if(dfs(1)) puts("TAK");
    else puts("NIE");
}```