[BZOJ2938] 病毒

偏执的太偏执、 2021-11-09 09:10 273阅读 0赞

# D. 病毒 #

#### 题目描述 ####

**原题来自：POI 2000**

二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。

示例：例如如果 \{011,11,00000\}\\\{011, 11, 00000\\\}\{ 011,11,00000\} 为病毒代码段，那么一个可能的无限长安全代码就是 010101⋯010101\\cdots 010101⋯。如果 \{01,11,000000\}\\\{01, 11, 000000\\\}\{ 01,11,000000\} 为病毒代码段，那么就不存在一个无限长的安全代码。

请写一个程序，读入病毒代码，判断是否存在一个无限长的安全代码，将结果输出。

#### 输入格式 ####

第一行包括一个整数 nnn，表示病毒代码段的数目；

以下的 nnn 行，每一行都包括一个非空的 010101 字符串——就是一个病毒代码段。

#### 输出格式 ####

第一行输出一个单词。假如存在这样的代码，则输出 `TAK`，否则输出 `NIE`。

#### 样例 ####

#### 样例输入 ####

3
    01 
    11 
    00000

#### 样例输出 ####

NIE

#### 数据范围与提示 ####

对于全部数据，所有病毒代码段的总长度不超过 3×1044。

对trie图的理解还是没有那么透彻啊(以前就只是知道他比trie树快…)。

安全的串可以在AC自动机上在不匹配单词终点的情况下无限匹配（颓题解之前就想到这里）， 在trie图上，如果能无线匹配那么意味着trie图上有环，dfs判环即可。

注意还有两个剪枝（zz的我刚开始居然用队列模拟深搜…）：

1.单词终点不能走，那么fail指向单词终点的点也不能走。设一个单词终点为x，y->fail=x，那么root~x为root~y的后缀，y也不能走。将x设为危险节点，fail指向x的y也是危险节点，同理所有fail指向危险节点的点都是危险节点（之前一直不能理解这玩意儿有啥用），dfs时将危险节点剪掉。

2.由于一个节点可能会搜多次，所以将搜索过但是return 0的节点标记，剪掉。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    using namespace std;
    struct trie
    {
        int count;
        bool pd,danger,vis;
        trie *next[2],*fail;
        trie()
        {
            count=0;pd=0;danger=0;vis=0;
            next[1]=next[2]=fail=NULL;
        }
    }*q[100000],*root=new trie();
    int head,tail;
    
    void insert(char s[],trie *root)
    {
        trie *p=root;
        int i=0,index;
        while(s[i])
        {
            index=s[i]-'0';
            if(p->next[index]==NULL)p->next[index]=new trie();
            p=p->next[index];
            i++;
        }
        p->count++;
        p->danger=1;
    }
    void build_ac(trie *root)
    {
        q[++tail]=root;
        while(head!=tail)
        {
            trie *p=q[++head];
            trie *temp=NULL;
            for(int i=0;i<=1;i++)
            if(p->next[i])
            {
                if(p==root)      p->next[i]->fail=p;
                else            
                {
                    p->next[i]->fail=p->fail->next[i];
                    if(p->fail->next[i]->danger)p->next[i]->danger=1;
                }    
                q[++tail]=p->next[i];
            }
            else
                if(p==root)       p->next[i]=root;
                else           p->next[i]=p->fail->next[i];
        }
    }
    bool dfs(trie *p)
    {
        p->pd=1;
        for(int i=0;i<=1;i++)
        {
            if(p->next[i]->pd)return 1;
            if(p->next[i]->danger || p->next[i]->vis)continue;
            if(dfs(p->next[i]))return 1;
            p->next[i]->vis=1;
        }    
        p->pd=0;
        return 0;
    }
    int n;
    char keyword[30010];
    char str[100000];
    signed main()
    {
        //freopen("in.txt","r",stdin);
    
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            scanf("%s",keyword);
            insert(keyword,root);
        }
        build_ac(root);
        if(dfs(root))cout<<"TAK";
        else           cout<<"NIE";
    }

转载于:https://www.cnblogs.com/Al-Ca/p/11056852.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/193bdafdf0074cdcafb23767b676db7d.png