BZOJ2938【POI2000】病毒 < AC自动机 >

Problem

【POI2000】病毒

$\mathrm{Time\;Limit:\;1\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。
示例：
如果$\lbrace011, 11, 00000\rbrace$为病毒代码段，那么一个可能的无限长安全代码就是$010101\cdots$。
如果$\lbrace01, 11, 000000\rbrace$为病毒代码段，那么就不存在一个无限长的安全代码。
任务：
请写一个程序

• 读入病毒代码
• 判断是否存在一个无限长的安全代码
• 将结果输出

Input

第一行包括一个整数$n$，表示病毒代码段的数目。
以下的$n$行每一行都包括一个非空的$01$字符串就是一个病毒代码段。
所有病毒代码段的总长度不超过$30000$。

Output

一行输出一个单词：
$\mathrm{TAK}$：存在这样的代码
$\mathrm{NIE}$：不存在这样的代码

Sample Input

3
01
11
00000

Sample Output

NIE

标签：AC自动机

Solution

首先显然需要建$\mathrm{AC}$自动机。
然后，在此$\mathrm{AC}$自动机形成的$\mathrm{DAG}$上，一个符合题意的无限长的串一定对应一个环，并且换上没有任何一个结点有结束标记。因此直接在$\mathrm{DAG}$上$\mathrm{DFS}$，暴力找解即可。

Code

#include <bits/stdc++.h>
#define MAX_N 30000
using namespace std;
int n, rt, cnt, tr[MAX_N+5][2], fail[MAX_N+5];
char s[MAX_N+5]; bool end[MAX_N+5], mrk[MAX_N+5], ins[MAX_N+5];
void init() {rt = ++cnt, tr[0][0] = tr[0][1] = rt;}
void insert() {
    int cur = rt, len = (int)strlen(s);
    for (int i = 0; i < len; cur = tr[cur][s[i++]-'0'])
        if (!tr[cur][s[i]-'0']) tr[cur][s[i]-'0'] = ++cnt;
    end[cur] = true;
}
void setFail() {
    queue <int> que; que.push(rt);
    while (!que.empty()) {
        int u = que.front(); que.pop();
        if (!tr[u][0]) tr[u][0] = tr[fail[u]][0];
        else
            que.push(tr[u][0]), 
            fail[tr[u][0]] = tr[fail[u]][0], 
            end[tr[u][0]] |= end[tr[fail[u]][0]];
        if (!tr[u][1]) tr[u][1] = tr[fail[u]][1];
        else
            que.push(tr[u][1]), 
            fail[tr[u][1]] = tr[fail[u]][1], 
            end[tr[u][1]] |= end[tr[fail[u]][1]];
    }
}
bool DFS(int u) {
    if (end[u]) return false;
    ins[u] = mrk[u] = true;
    if (ins[tr[u][0]]) return true;
    if (ins[tr[u][1]]) return true;
    if (!mrk[tr[u][0]] && DFS(tr[u][0])) return true;
    if (!mrk[tr[u][1]] && DFS(tr[u][1])) return true;
    ins[u] = false;	return false;
}
int main() {
    scanf("%d", &n), init();
    for (int i = 1; i <= n; i++)
        scanf("%s", s), insert();
    setFail();
    return puts(DFS(rt) ? "TAK" : "NIE"), 0;
}