【洛谷 P2444】 [POI2000]病毒（AC自动机）

题目链接

这么多字符串，肯定是自动机啦。
先建出AC自动机，然后怎么表示一个安全代码没有病毒代码呢？
就是存在一条路径不经过有病毒代码段结尾的节点呗。
所以呢？有环啊！dfs一下救星了。

#include <cstdio>
#include <queue>
#include <cstring>
#include <cstdlib>
using namespace std;
struct Node{
    int fail, next[2], num;
}AC[1000010];
int n, u, cnt;
queue <int> q;
int vis[1000010], mark[1000010];
char a[2000010];
void insert(){
    int len = strlen(a + 1), w;
    u = 0;
    for(int i = 1; i <= len; ++i){
        w = a[i] - '0';
        if(!AC[u].next[w])
          AC[u].next[w] = ++cnt;
        u = AC[u].next[w];
    }
    AC[u].num = 1;
}
void BuildFail(){
    u = 0;
    for(int i = 0; i < 2; ++i)
       if(AC[u].next[i])
         q.push(AC[u].next[i]);
    while(q.size()){
        u = q.front(); q.pop();
        AC[u].num |= AC[AC[u].fail].num;
        for(int i = 0; i < 2; ++i)
           if(AC[u].next[i]){
             q.push(AC[u].next[i]);
             AC[AC[u].next[i]].fail = AC[AC[u].fail].next[i];
           }
           else
             AC[u].next[i] = AC[AC[u].fail].next[i];
    }
}
void dfs(int x){
    if(AC[x].num) return;
    if(vis[x]){ printf("TAK\n"); exit(0); }
    if(mark[x]) return;
    vis[x] = mark[x] = 1;
    for(int i = 0; i < 2; ++i)
       if(AC[x].next[i])
         dfs(AC[x].next[i]);
    vis[x] = 0;
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%s", a + 1);
        insert();
    }
    BuildFail();
    dfs(0);
    printf("NIE\n");
    return 0;
}

【洛谷 P2444】 [POI2000]病毒（AC自动机）

原文：https://www.cnblogs.com/Qihoo360/p/10883943.html