[POI2000] 病毒 - AC自动机

套路性地打标记以后沿着fail树下传

然后找有没有与根连通的白色环路即可

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int ch[N][2],fi[N],val[N],n,m,t1,t2,t3,t4,ind,vis[N],flag;

void ins(char *s) {
    int len=strlen(s),p=0;
    for(int i=0;i<len;i++) {
        if(ch[p][s[i]-'0']==0) ch[p][s[i]-'0']=++ind;
        p=ch[p][s[i]-'0'];
    }
    val[p]++;
}

void build() {
    queue <int> q;
    for(int i=0;i<2;i++) if(ch[0][i]) q.push(ch[0][i]);
    while(!q.empty()) {
        int p=q.front(); q.pop();
        val[p]|=val[fi[p]];
        for(int i=0;i<2;i++)
            if(ch[p][i]) fi[ch[p][i]]=ch[fi[p]][i],q.push(ch[p][i]);
            else ch[p][i]=ch[fi[p]][i];
    }
}

void dfs(int p) {
    if(val[p]) {vis[p]=2; return;}
    vis[p]=1;
    for(int i=0;i<2 && !flag;i++) {
        if(vis[ch[p][i]]==0) {
            dfs(ch[p][i]);
        }
        else if(vis[ch[p][i]]==1) {
            flag=1;
        }
    }
    vis[p]=2;
}

char str[N];

int main() {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>str,ins(str);
    build();
    dfs(0);
    cout<<(flag?"TAK":"NIE")<<endl;
}

[POI2000] 病毒 - AC自动机

原文：https://www.cnblogs.com/mollnn/p/12263031.html