Cod sursa(job #2851514)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 18 februarie 2022 19:17:05
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.81 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");

class AhoCorasick {
    struct Node {
        int ends, link, next[26];
        int fath, code, tran[26];
        Node(int fath, int code) :
            ends(0), link(-1), fath(fath), code(code) {
                fill(begin(next), end(next), -1);
                fill(begin(tran), end(tran), -1);
            }
    };
    vector<int> where;
    vector<Node> trie{1, Node(-1, -1)};

    int getLink(int node) {
        if (trie[node].link == -1)
            trie[node].link
                = !node || !trie[node].fath
                ? 0
                : getTran(getLink(trie[node].fath), trie[node].code);
        return trie[node].link;
    }

    int getTran(int node, int code) {
        if (trie[node].tran[code] == -1)
            trie[node].tran[code]
                = trie[node].next[code] != -1
                ? trie[node].next[code]
                : node
                    ? getTran(getLink(node), code)
                    : 0;
        return trie[node].tran[code];
    }

public:
    void insert(string str) {
        int node = 0;
        for (char chr : str) {
            const int code = chr - 'a';
            if (trie[node].next[code] == -1) {
                trie[node].next[code] = trie.size();
                trie.emplace_back(node, code);
            }
            node = trie[node].next[code];
        }
        where.push_back(node);
    }

    void build() {
        for (int node = 0; node < int(trie.size()); node++) {
            getLink(node);
            for (int code = 0; code < 26; code++)
                getTran(node, code);
        }
    }

    vector<int> solve(string str) {
        int node = 0;
        for (char chr : str) {
            node = trie[node].tran[chr - 'a'];
            trie[node].ends++;
        }
        vector<int> order(1, 0);
        for (int i = 0; i < int(order.size()); i++) {
            const int node = order[i];
            for (int code = 0; code < 26; code++)
                if (trie[node].next[code] != -1)
                    order.push_back(trie[node].next[code]);
        }
        reverse(order.begin(), order.end());
        for (int node : order)
            trie[trie[node].link].ends += trie[node].ends;
        vector<int> ans(where.size());
        for (int i = 0; i < int(where.size()); i++)
            ans[i] = trie[where[i]].ends;
        return ans;
    }
};

int main() {
    AhoCorasick aho;
    string str; fin >> str;

    int n; fin >> n;
    for (int i = 0; i < n; i++) {
        string pat; fin >> pat;
        aho.insert(pat);
    }
    aho.build();

    auto frq = aho.solve(str);
    for (int i = 0; i < n; i++)
        fout << frq[i] << '\n';
    return 0;
}