MENU

洛谷P2444/BZOJ2938/LibreOJ#10062/COGS703 [POI2000]病毒

洛谷P2444

BZOJ2938

LibreOJ#10062

COGS703

AC自动机建图后找环。

#include<iostream>
#include<string>
#include<queue>
using namespace std;
int n, nxt[30001][2], fail[30001] = { 1 }, d[30001], q[30001], cnt = 1, vis[30001], ins[30001];
string s;
int dfs(int x) {
    ins[x] = 1;
    for (int i = 0; i < 2; ++i) {
        int v = nxt[x][i];
        if (ins[v])return 1;
        if (vis[v] || d[v])continue;
        vis[v] = 1;
        if (dfs(v))return 1;
    }
    ins[x] = 0;
    return 0;
}
int main() {
    nxt[0][0] = nxt[0][1] = 1, ios::sync_with_stdio(0), cin.tie(0), cin >> n;
    while (n--) {
        cin >> s;
        int now = 1;
        for (char i : s) {
            if (!nxt[now][i - '0'])nxt[now][i - '0'] = ++cnt;
            now = nxt[now][i - '0'];
        }
        d[now] = 1;
    }
    queue<int>q;
    q.push(1);
    while (q.size()) {
        int now = q.front();
        q.pop();
        for (int i = 0; i < 2; ++i) {
            int v = nxt[now][i];
            if (!v) { nxt[now][i] = nxt[fail[now]][i]; continue; }
            int k = fail[now];
            while (!nxt[k][i])k = fail[k];
            fail[v] = nxt[k][i], d[v] |= d[nxt[k][i]], q.push(v);
        }
    }
    cout << (dfs(1) ? "TAK" : "NIE");
}