[BZOJ2938][Poi2000]病毒

Bertha 。 2023-06-05 12:39 20阅读 0赞

题目描述：[https://www.lydsy.com/JudgeOnline/problem.php?id=2938][https_www.lydsy.com_JudgeOnline_problem.php_id_2938]

解析：做了这个题对AC自动机有了更深的理解。先建立补全的AC自动机，发现如果有无限长的串使得任意一个原串都不在这个串中，一定满足这个补全的AC自动机在不经过叶子结点的情况下有环。简略证明一下：发现一个点跳fail的过程的实质即为在一个字符串后面增加一个字符，如果在不经过叶子结点的情况下有环，说明这个串可以无限延伸。怎么在图中判环呢？可以从原点开始dfs，建立两个标记数组，一个用来标记走没走过，走过的点不能再次走，否则会出现死循环。一个用来标记是否在栈中，如果重复出现在栈中则说明有换，回溯的时候记得要把标记清空。

细节：1.这个补全的图中可以有自环，循环节为0或1。2.叶子结点的标记要下传。3.不要在某谷交，数据很水。

附上代码：

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

#include<bits/stdc++.h>
    using namespace std;
    
    const int MAXL=30005,MAXN=2005;
    char s[MAXL];
    int n;
    int go[MAXN*10][2];
    int ndnum=0;
    int fail[MAXN*20];
    bool is_end[MAXN*20];
    queue<int> q;
    int v[MAXN*20],used[20*MAXN];
    
    void insert(){
        int len=strlen(s+1);
        int now=0;
        for(int i=1;i<=len;i++){
            int c=s[i]-'0';
            if(!go[now][c]) go[now][c]=++ndnum;
            now=go[now][c];
        }
        is_end[now]=1;
    }
    
    void get_fail(){
        for(int i=0;i<=1;i++) 
            if(go[0][i]) q.push(go[0][i]);
        while(q.size()){
            int x=q.front();q.pop();
            for(int i=0;i<=1;i++){
                if(go[x][i]){
                    int t=fail[x];
                    fail[go[x][i]]=go[t][i];
                    q.push(go[x][i]);
                    is_end[go[x][i]]|=is_end[go[t][i]];
                }
                else 
                    go[x][i]=go[fail[x]][i];
            }
        }
    }
    
    void dfs(int x){
        v[x]=1;used[x]=1;
        for(int i=0;i<=1;i++){
            if(!is_end[go[x][i]]){
                if(v[go[x][i]]){
                    printf("TAK");
                    exit(0);
                }
                else if(!used[go[x][i]]) dfs(go[x][i]);
            }
        }
        v[x]=0;
    }
    
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%s",s+1);
            insert();
        }
        get_fail();
        dfs(0);
        printf("NIE");
        return 0;
    }

转载于:https://www.cnblogs.com/JoshDun/p/11210269.html

[https_www.lydsy.com_JudgeOnline_problem.php_id_2938]: https://www.lydsy.com/JudgeOnline/problem.php?id=2938
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/b1cd99a767b1409fb28b5262f8a0e053.png