fork download
copy 
/*
 E. Вирусы

Комитет По Исследованию Бинарных Вирусов обнаружил, что некоторые последовательности единиц и нулей являются кодами вирусов. Комитет изолировал набор кодов вирусов. Последовательность из единиц и нулей называется безопасной, если никакой ее подотрезок (т.е. последовательность из соседних элементов) не является кодом вируса. Сейчас цель комитета состоит в том, чтобы установить, существует ли бесконечная безопасная последовательность из единиц и нулей.

Указание: используйте алгоритм Ахо-Корасик.

Формат ввода
Первая строка входного файла virus.in содержит одно целое число n, равное количеству всех вирусных кодов. Каждая из следующих n строк содержит непустое слово, составленное из символов 0 и 1 — код вируса. Суммарная длина всех слов не превосходит 30 000.

Формат вывода
Первая и единственная строка выходного файла должна содержать слово:

TAK — если бесконечная, безопасная последовательность из нулей и единиц сушествует;
NIE — в противном случае.

 in
 3
01
11
00000

out
 NIE

 in
 3
011
11
0000

 out
 TAK

 */

#include <ctime>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <set>
#include <string>
#include <unistd.h>

using namespace std;

struct Vertex {
    string value;
    int suffixLink = 0;
    int parent;
    bool isTerminal = false;

    vector<int> childrenId;
};

void createSuffixLinks(vector<Vertex> &tree, int id) {
    string letter;
    letter += tree[id].value;

    int vertexToCheck = tree[tree[id].parent].suffixLink;

    if (vertexToCheck == -1)
        createSuffixLinks(tree, tree[id].parent);

    while (vertexToCheck != 0) {
        for (int child : tree[vertexToCheck].childrenId) {
            if (tree[child].value == letter) {
                tree[id].suffixLink = child;
                return;
            }
        }
        if (tree[vertexToCheck].suffixLink == -1)
            createSuffixLinks(tree, vertexToCheck);

        vertexToCheck = tree[vertexToCheck].suffixLink;
    }

    for (int child : tree[0].childrenId) {
        if (tree[child].value == letter) {
            tree[id].suffixLink = child;
            return;
        }
    }

    tree[id].suffixLink = 0;

    //cout << id << ' ' << tree[id].value << ' ' << tree[id].suffixLink << '\n';
}

vector<Vertex> createTree(const vector<string> &lines) {
    setbuf(stdout, nullptr);
    for (string line : lines) {
        cout << line << '\n';
    }
    cout << '\n';

    vector<Vertex> tree;
    tree.push_back({"", 0, -1, false});
    int freeId = 1;

    for (string line : lines) {
        int parent = 0;
        for (size_t i = 0; i < line.size(); ++i) {
            string letter;
            letter += line[i];
            bool flag = true;
            for (int id : tree[parent].childrenId) {
                if (tree[id].value == letter) {
                    tree[id].isTerminal = (i == line.size() - 1);
                    parent = id;
                    flag = false;
                    break;
                }
            }
            if (flag) {
                tree.push_back({letter, -1, parent, i == line.size() - 1});
                tree[parent].childrenId.push_back(freeId);
                parent = freeId;
                ++freeId;
            }
        }
    }

    for (int id : tree[0].childrenId) {
        tree[id].suffixLink = 0;
    }

    for (size_t i = 1; i < tree.size(); ++i) {
        if (tree[i].suffixLink == -1) {
            //cout << i << '\n';
            createSuffixLinks(tree, i);
        }
    }

    return tree;
}

int moveToLetter(const vector<Vertex> &tree, const Vertex &from, const string &letter) {
    for (int child : from.childrenId) {
        if (tree[child].value == letter) {
            return child;
        }
    }

    if (from.value.empty())
        return 0;

    return moveToLetter(tree, tree[from.suffixLink], letter);
}

bool checkCycle(const vector<Vertex> &tree, vector<int> visited, int v) {
    if (tree[v].isTerminal) {
        visited[v] = 2;
        return false;
    }
    // cout << v << '\n';
    visited[v] = 1;
    vector<string> alphabet({"0", "1"});

    for (string letter : alphabet) {
        int to = moveToLetter(tree, tree[v], letter);
        if (to == v)
            return true;

        if (!visited[to]) {
            if (checkCycle(tree, visited, to))
                return true;
        } else if (visited[to] == 1) {
            return true;
        }
    }

    visited[v] = 2;
    return false;
}

void stressTest(int seed) {
    srand(seed);

    vector<string> viruses;
    for (int i = 0; i < 4; ++i) {
        string virus;
        for (int j = 0; j < 6
        ; ++j) {
            virus += char('0' + rand() % 2);
        }
        viruses.push_back(virus);
    }

    setbuf(stdout, nullptr);
    for (string line : viruses) {
        cout << line << '\n';
    }
    cout << '\n';

    vector<Vertex> tree = createTree(viruses);

    for (int i = 0; i < tree.size(); ++i)
        cout << i << ' ' << tree[i].value << ' ' << tree[i].suffixLink << '\n';

    vector<int> visited(tree.size());

    for (int v = 0; v < tree.size(); ++v) {
        if (!visited[v]) {
            if (checkCycle(tree, visited, v)) {
                cout << "TAK\n";
                return;
            }
        }
    }
    cout << "NIE\n";
}

int main() {
    int virusesCount;
    cin >> virusesCount;
    vector<string> viruses;
    for (int i = 0; i < virusesCount; ++i) {
        string virus;
        cin >> virus;
        viruses.push_back(virus);
    }

    vector<Vertex> tree = createTree(viruses);

    for (int i = 0; i < tree.size(); ++i)
        cout << i << ' ' << tree[i].value << ' ' << tree[i].suffixLink << '\n';

    vector<int> visited(tree.size());

    for (int v = 0; v < tree.size(); ++v) {
        if (!visited[v]) {
            if (checkCycle(tree, visited, v)) {
                cout << "TAK";
                return 0;
            }
        }
    }
    cout << "NIE";
}
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
6
000
111
001
010
011
100
stdout
copy 
000
111
001
010
011
100

0  0
1 0 0
2 0 1
3 0 2
4 1 0
5 1 4
6 1 5
7 1 8
8 1 4
9 0 11
10 1 5
11 0 1
12 0 2
NIE
https://ideone.com/HNNZ6G
language:
C++14 (gcc 8.3)
created:
23 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!