P2444 [POI2000]病毒

· · 题解

P2444 [POI2000]病毒

题意:给01模板串,判断是否存在无限长01串不包含任何一个模板串

一眼看过去没头绪,还以为挺难

一看是蓝题,

那我就画画图吧

画了只AC自动机

然后就发现只要dfs且怎么走都会碰到end时就不存在安全代码

那就找环呗，只要这个环上没有病毒的结尾就可以一直循环

开始想的是把所有end及其相关边去掉看看有没有环

但题目只求存在性

那就dfs重复到达一个节点就退出来嘛

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=5000000+5;
template<class T>inline void read(T &num){
    char ch;
    while(!isdigit(ch=getchar()));
    num=ch-'0';
    while(isdigit(ch=getchar()))num=num*10+ch-'0';
}

int tri[N][2],is_end[N],fail[N],vis[N],totn,n;
inline void Insert(char s[]){
    int len=strlen(s),x=0;
    for(int p=0;p<len;++p){
        int ch=s[p]-'0';
        if(tri[x][ch]==0)tri[x][ch]=++totn;
        x=tri[x][ch];
    }
    is_end[x]=1;
}

queue<int> que;
inline void Fail(){
    int x=0;
    if(tri[x][0])que.push(tri[x][0]);
    if(tri[x][1])que.push(tri[x][1]);
    while(que.size()){
        x=que.front();que.pop();
        if(is_end[fail[x]])is_end[x]=1;
//printf("fail[%d]=%d\n",x,fail[x]);
        if(tri[x][0])fail[tri[x][0]]=tri[fail[x]][0],que.push(tri[x][0]);
        else tri[x][0]=tri[fail[x]][0];
        if(tri[x][1])fail[tri[x][1]]=tri[fail[x]][1],que.push(tri[x][1]);
        else tri[x][1]=tri[fail[x]][1];
    }
}

bool dfs(int x=0){
//printf("vis[%d]=%d\n",x,vis[x]);
    if(vis[x])return true;
    vis[x]=1;
//printf("tri[x]=(%d,%d)\n",tri[x][0],tri[x][1]);
//printf("is_end(%d,%d)\n",is_end[tri[x][0]],is_end[tri[x][1]]);
    if(!is_end[tri[x][0]])if(dfs(tri[x][0]))return true;
    if(!is_end[tri[x][1]])if(dfs(tri[x][1]))return true;
    vis[x]=0;
    return false;
}

char s[30000+5];
int main(){
    read(n);
    for(int i=1;i<=n;++i){
        scanf("%s",s);
        Insert(s);
    }
    Fail(); 
    printf("%s",dfs()?"TAK":"NIE");
    return 0;
}