Cod sursa(job #3323387)

Utilizator Carnu_EmilianCarnu Emilian Carnu_Emilian Data 18 noiembrie 2025 11:04:28
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.27 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
typedef long long ll;
typedef long double ld;

const int N = 1e2 + 5;
const int alpha = 26;
int n;
string s, t;

struct nod
{
    int cnt;
    nod *suflink, *v[alpha];
    nod()
    {
        cnt = 0;
        suflink = NULL;
        for (int i = 0; i < alpha; i++)
            v[i] = NULL;
    }
} *root, *termnodes[N];

bool haschild(nod *x, int a)
{
    return (x->v[a] == NULL) ? false : true;
}

nod* inserare() // string t
{
    nod *x = root;
    for (char c : t)
    {
        int a = c - 'a';
        if (!haschild(x, a))
            x->v[a] = new nod;
        x = x->v[a];
    }
    return x;
}

void solveprefix(nod *x, int a)
{
    nod *pref = x->suflink;
    while (pref != root && !haschild(pref, a))
        pref = pref->suflink;
    if (haschild(pref, a) && pref != x)
        x->v[a]->suflink = pref->v[a];
    else
        x->v[a]->suflink = root;
}

void build()
{
    root->suflink = root;
    queue<nod*> q;
    q.push(root);
    while (!q.empty())
    {
        nod *x = q.front();
        q.pop();
        for (int i = 0; i < alpha; i++)
            if (haschild(x, i))
            {
                solveprefix(x, i);
                q.push(x->v[i]);
            }
    }
}

void solve()
{
    nod *x = root;
    for (char c : s)
    {
        int a = c - 'a';
        while (x != root && !haschild(x, a))
            x = x->suflink;
        if (haschild(x, a))
            x = x->v[a];
        x->cnt++;
    }
    vector<nod*> bfsOrder;
    bfsOrder.push_back(root);

    for (int i = 0; i < bfsOrder.size(); i++)
    {
        nod* node = bfsOrder[i];

        for (int j = 0; j < alpha; j++)
            if (haschild(node, j))
                bfsOrder.push_back(node->v[j]);
    }

    for (int i = bfsOrder.size() - 1; i >= 0; i--)
    {
        bfsOrder[i]->suflink->cnt += bfsOrder[i]->cnt;
    }
}

int main()
{
    fin >> s >> n;
    root = new nod;
    for (int i = 1; i <= n; i++)
    {
        fin >> t;
        termnodes[i] = inserare();
    }
    build();
    solve();
    for (int i = 1; i <= n; i++)
        fout << termnodes[i]->cnt << '\n';
    return 0;
}