题解 P2444 【[POI2000]病毒】

· · 题解

I \mathrm{AC}自动机

约定在构造$\mathrm{AC}$自动机的过程中，$\mathrm{Trie}$树上的边和由于$\mathrm{AC}$自动机中这一句： ```cpp else ch[x][i]=ch[fail[x]][i]; ``` 所新建的边为实边。 也就是$x$到$ch[x][0]$和$ch[x][1]$的边为实边。 --- ## II 危险！ 什么样的字符串是有病毒的？包含了某个模式串的文本串。 这样的文本串一定在AC自动机上经过一个字符串的结尾节点。 我们称这样的节点是危险的。 --- ## III 解法 想象一下，假如在AC自动机上有一个环，我就可以让这个文本串一直在这个环上跑，转啊转啊转。 就像最短路有了负环一样。 所以，只要在AC自动机上，存在一个环，使得这个环上和从根到这个环的路径上，所有的点都不是危险节点，就有解，否则无解。 --- ## IV $\mathrm{code} 
#include<bits/stdc++.h>
using namespace std;

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') {
        ch=getchar();fh=-1;
    }
    else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=fh;
}

int n;
int ch[300000][2],tot;
bool ed[300000];
int fail[300000],root;
string s;

int chk(char s){
    return s-'0';
}

void insert(){
    int siz=s.size();int p=root;
    for(int i=0;i<siz;i++){
        int d=chk(s[i]);
        if(!ch[p][d]) ch[p][d]=++tot;
        p=ch[p][d];
    }
    ed[p]=1;
}

void pre(){
    queue<int>q;
    for(int i=0;i<2;i++){
        if(ch[root][i]) fail[ch[root][i]]=root,q.push(ch[root][i]);
    }
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=0;i<2;i++){
            if(ch[x][i]){
                fail[ch[x][i]]=ch[fail[x]][i],q.push(ch[x][i]);
                if(ed[ch[fail[x]][i]]) ed[ch[x][i]]=1; 
            }
            else ch[x][i]=ch[fail[x]][i];
        }
    }
}

bitset<300000>ins;

void dfs(int x){
    if(ins[x]){
        puts("TAK");exit(0);
    }
    ins[x]=1;
    for(int i=0;i<2;i++){
        if(!ch[x][i]||ed[ch[x][i]]) continue;
        dfs(ch[x][i]);
    }
    ins[x]=0;
}

int main(){
    read(n);
    for(register int i=1;i<=n;i++){
        cin>>s;insert();
    }
    pre();dfs(root);
    puts("NIE");
    return 0;
}