Cod sursa(job #3156849)

Utilizator AleXutzZuDavid Alex Robert AleXutzZu Data 13 octombrie 2023 14:13:42
Problema Aho-Corasick Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.78 kb
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <fstream>

struct Trie {
private:
    constexpr static const int K = 26;

    struct Vertex {
        std::vector<int> next;
        int output = -1;
        int fail = -1;

        Vertex() {
            next.resize(K, -1);
        }
    };

    std::vector<Vertex> tree;

    int &next(int node, char c) {
        return tree[node].next[c - 'a'];
    }

    int &output(int node) {
        return tree[node].output;
    }

    int &fail(int node) {
        return tree[node].fail;
    }

    void push_links() {
        std::queue<int> queue;

        for (char i = 'a'; i <= 'z'; ++i) {
            int s = next(0, i);
            if (s > 0) {
                queue.push(s);
                fail(s) = 0;
            }
        }

        while (!queue.empty()) {
            int top = queue.front();
            queue.pop();

            for (char i = 'a'; i <= 'z'; ++i) {
                int s = next(top, i);
                if (s == -1) continue;

                queue.push(s);
                int state = fail(top);
                while (next(state, i) == -1) state = fail(state);
                fail(s) = next(state, i);
            }
        }
    }


public:
    Trie() {
        tree.emplace_back();
    }

    void add_word(const std::string &str, int idx) {
        int node = 0;
        for (auto i: str) {
            if (next(node, i) == -1) {
                next(node, i) = (int) tree.size();
                tree.emplace_back();
            }
            node = next(node, i);
        }
        output(node) = idx;
    }

    void compute() {
        fail(0) = 0;
        for (char i = 'a'; i <= 'z'; ++i) {
            if (next(0, i) == -1) next(0, i) = 0;
        }

        push_links();
    }

    void advance(int &state, char c, const std::function<void(int)> &dispatch) {
        while (next(state, c) == -1) state = fail(state);
        state = next(state, c);

        dispatch(output(state));

        int cpy = fail(state);
        while (cpy != 0) {
            dispatch(output(cpy));
            cpy = fail(cpy);
        }
    }
};

struct InputParser {
private:
    FILE *file;
    int ptr{};
    char *buffer;

    char read() {
        if (ptr == 4096) {
            fread(buffer, 1, 4096, file);
            ptr = 0;
        }
        return buffer[ptr++];
    }

public:
    explicit InputParser(const std::string &file) {
        this->file = fopen(file.c_str(), "r");
        ptr = 4096;
        buffer = new char[4096];
    }

    inline InputParser &operator>>(char &c) {
        c = read();
        return *this;
    }

    inline InputParser &operator>>(std::string &str) {
        char c;
        while (!std::isalpha(c = read()));
        str += c;
        while (std::isalpha(c = read())) {
            str += c;
        }
        return *this;
    }

    inline InputParser &operator>>(int &n) {
        char c;
        while (!std::isdigit(c = read()));
        n = c - '0';
        while (std::isdigit(c = read())) n = n * 10 + c - '0';
        return *this;
    }
};

int main() {
    InputParser input("ahocorasick.in");
    std::ofstream output("ahocorasick.out");
    Trie trie;
    std::string s;
    int n;
    input >> s >> n;

    std::unordered_map<std::string, int> map;

    std::vector<std::string> words(n);
    for (int i = 0; i < n; ++i) {
        input >> words[i];

        if (map[words[i]] == 0) map[words[i]] = i + 1;
    }

    for (const auto &[str, idx]: map) {
        trie.add_word(str, idx);
    }

    std::vector<int> ans(n + 1);

    auto dispatch = [&ans](int idx) {
        if (idx != -1) ans[idx]++;
    };

    int state = 0;
    trie.compute();
    for (char i: s) {
        trie.advance(state, i, dispatch);
    }

    for (int i = 0; i < n; ++i) output << ans[map[words[i]]] << '\n';
    return 0;
}