Cod sursa(job #3308250)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 23 august 2025 20:34:35
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
#include <fstream>
#include <queue>

using namespace std;

const string txt = "ahocorasick";

ifstream f(txt + ".in");
ofstream g(txt + ".out");

struct trie {
    int cnt;
    trie* v[26];
    trie* edge;

    trie() {
        cnt = 0; edge = NULL;
        for (int i = 0; i < 26; i++) v[i] = NULL;
    }
};

trie* root; trie* cuv[105];
int n; string s;
vector<trie*> nr;
queue<trie*> q;

static trie* add(string &x, int p, trie* nod)
{
    if (p >= x.size())
        return nod;

    int ind = x[p] - 'a';

    if (!nod -> v[ind])
        nod -> v[ind] = new trie;

    return add(x, p + 1, nod -> v[ind]);
}

static void bfs()
{
    queue<trie*> q;
    while (!q.empty()) q.pop();

    q.push(root);
    while (!q.empty())
    {
        auto nod = q.front(); q.pop();
        nr.push_back(nod);

        for (int i = 0; i < 26; i++)
            if (nod -> v[i] && !nod -> v[i] -> edge)
            {
                auto idk = nod -> edge;
                while (idk && !idk -> v[i])
                    idk = idk -> edge;
            
                if (!idk) idk = root;
                else idk = idk -> v[i];

                nod -> v[i] -> edge = idk;
                q.push(nod -> v[i]);
            }
    }
}

static void update()
{
    while(nr.size())
    {
        auto nod = nr.back();
        nr.pop_back();

        if (nod -> edge)
            nod -> edge -> cnt += nod -> cnt;
    }
}

static void match()
{
    trie* nod = root;
    for (auto x : s)
    {
        int ind = x - 'a';
        while (nod && !nod -> v[ind])
            nod = nod -> edge;

        if (!nod) nod = root;
        else nod = nod -> v[ind];

        nod -> cnt++;
    }
}

int main()
{
    f >> s >> n;
    root = new trie;
    for (int i = 1; i <= n; i++)
    {
        string x; f >> x;
        cuv[i] = add(x, 0, root);
    }

    bfs();
    match();
    update();

    for (int i = 1; i <= n; i++)
        g << cuv[i] -> cnt << '\n';
    return 0;
}