DDOSvoid's Blog

Luogu P2444 [POI2000]病毒

发表于 更新于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

题目描述

https://www.luogu.com.cn/problem/P2444

简要题意：给定 $n$ 个字符串，求是否存在一个无限长的字符串，满足不存在这 $n$ 个串中的任何一个串是其子串

$len\le 3\times 10^4$

Solution

我们模拟文本串在匹配时所进行的操作

发现只要将 $ext$ 标记沿着 $fail$ 树下传

然后在 $AC$ 自动机上走的时候不走有标记的点判断是否能够走一个环

有向图判环的话只需要注意回边即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define maxn 30010
using namespace std;

int n;

char s[maxn];

#define ch s[i] - '0'
struct AC_automaton {
    int nxt[2], fail; bool ext;
} T[maxn]; int top = 1, rt = 1;
void insert(char *s) {
    int now = rt, l = strlen(s);
    for (int i = 0; i < l; ++i) {
        if (!T[now].nxt[ch]) T[now].nxt[ch] = ++top;
        now = T[now].nxt[ch];
    } T[now].ext = 1; 
}

queue<int> Q;
void init_fail() {
    for (int i = 0; i < 2; ++i) {
        int &u = T[rt].nxt[i];
        if (!u) { u = rt; continue; }
        T[u].fail = rt; Q.push(u); 
    }
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (int i = 0; i < 2; ++i) {
            int &v = T[u].nxt[i];
            if (!v) { v = T[T[u].fail].nxt[i]; continue; }
            T[v].fail = T[T[u].fail].nxt[i];
            T[v].ext |= T[T[v].fail].ext; 
            Q.push(v);
        }
    }
}

bool ins[maxn], vis[maxn];
bool dfs(int u) {
    ins[u] = vis[u] = 1;
    for (int i = 0; i < 2; ++i) {
        int v = T[u].nxt[i];
        if (ins[v]) return 1; 
        if (T[v].ext || vis[v]) continue;
        if (dfs(v)) return 1;
    }
    ins[u] = 0; 
    return 0;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) scanf("%s", s), insert(s);
    init_fail(); 
    if (dfs(rt)) puts("TAK");
    else puts("NIE"); 
    return 0;
}