Cod sursa(job #3366598)

Utilizator Cristian_NegoitaCristian Negoita Cristian_Negoita Data 2 octombrie 2026 16:09:29
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.52 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
const int SIGMA = 26, QUERIES = 2e5;
int ans[QUERIES];

class AhoCorasick
{
private:
    struct Node
    {
        Node *children[SIGMA], *link;
        int used = 0;
        vector<int> ending;
        Node()
        {
            fill(children, children + SIGMA, nullptr);
        }
    };
    Node *root = new Node;
    vector<Node*> order;

public:
    void adauga(const string &word, int id)
    {
        Node *node = root;
        for(char ch : word)
        {
            if(node->children[ch - 'a'] == nullptr)
                node->children[ch - 'a'] = new Node;
            node = node->children[ch - 'a'];
        }
        node->ending.push_back(id);
    }

    void precalculare()
    {
        queue<Node*> Q({root});
        root->link = root;
        while(!Q.empty())
        {
            Node *node = Q.front(); Q.pop();
            order.push_back(node);
            for(int ch = 0; ch < SIGMA; ch++)
            {
                Node *child = node->children[ch];
                if(child == nullptr)
                    continue;
                Node *fall = node->link;
                while(fall != root && fall->children[ch] == nullptr)
                    fall = fall->link;

                if(fall->children[ch] != nullptr && fall->children[ch] != child)
                    child->link = fall->children[ch];
                else
                    child->link = root;

                Q.push(child);
            }
        }
    }

    void cauta(const string &text)
    {
        Node *node = root;
        for(char ch : text)
        {
            while(node != root && node->children[ch - 'a'] == nullptr)
                node = node->link;
            if(node->children[ch - 'a'] != nullptr)
                node = node->children[ch - 'a'];
            node->used++;
        }
        reverse(order.begin(), order.end());
        for(auto node : order)
        {
            for(int id : node->ending)
                ans[id] += node->used;
            node->link->used += node->used;
        }
    }
};

int main()
{
    int q;
    string text;
    fin >> text >> q;
    AhoCorasick aho;
    for(int i = 0; i < q; i++)
    {
        string word;
        fin >> word;
        aho.adauga(word, i);
    }
    aho.precalculare();
    aho.cauta(text);
    for(int i = 0; i < q; i++)
        fout << ans[i] << "\n";

    return 0;
}