Cod sursa(job #3208799)

Utilizator SSKMFSS KMF SSKMF Data 1 martie 2024 09:30:07
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.47 kb
#include <fstream>
using namespace std;

ifstream cin ("ahocorasick.in");
ofstream cout ("ahocorasick.out");

struct Aho_Corasick {
    Aho_Corasick *urmatorul[26] = { } , *anterior = NULL;
    int termen = 0;
} *aparitii = new Aho_Corasick , *locatie[101] , *coada[1000001];

char sir[1000001];

Aho_Corasick* Insert (const char sir[])
{
    Aho_Corasick *nod_actual = aparitii;
    for (int indice = 0 ; sir[indice] ; nod_actual = nod_actual -> urmatorul[sir[indice++] - 'a']) {
        if (!nod_actual -> urmatorul[sir[indice] - 'a'])
            { nod_actual -> urmatorul[sir[indice] - 'a'] = new Aho_Corasick; }
    }

    return nod_actual;
}

void Solve ()
{
    int stanga = 1 , dreapta = 0;
    aparitii -> anterior = aparitii;
    for (coada[++dreapta] = aparitii ; stanga <= dreapta ; stanga++)
    {
        Aho_Corasick *nod_actual = coada[stanga];
        for (int indice = 0 ; indice < 26 ; indice++) {
            if (nod_actual -> urmatorul[indice])
            {
                Aho_Corasick *nod_vecin = nod_actual -> urmatorul[indice] , *candidat = nod_actual -> anterior;
                while (candidat != aparitii && !candidat -> urmatorul[indice])
                    { candidat = candidat -> anterior; }

                if (candidat -> urmatorul[indice] && candidat -> urmatorul[indice] != nod_vecin)
                    { candidat = candidat -> urmatorul[indice]; }

                nod_vecin -> anterior = candidat;
                coada[++dreapta] = nod_vecin;
            }
        }
    }
{
    Aho_Corasick *nod_actual = aparitii;
    for (int indice = 0 ; sir[indice] ; indice++)
    {
        while (nod_actual != aparitii && !nod_actual -> urmatorul[sir[indice] - 'a'])
            { nod_actual = nod_actual -> anterior; }

        if (nod_actual -> urmatorul[sir[indice] - 'a'])
            { nod_actual = nod_actual -> urmatorul[sir[indice] - 'a']; }

        nod_actual -> termen++;
    }
}
    for (stanga = dreapta ; stanga > 1 ; stanga--)
        { coada[stanga] -> anterior -> termen += coada[stanga] -> termen; }
}

int main ()
{
    int numar_cuvinte;
    cin >> sir >> numar_cuvinte;

    for (int indice = 1 ; indice <= numar_cuvinte ; indice++)
        { char cuvant[10001]; cin >> cuvant; locatie[indice] = Insert(cuvant); }

    Solve();

    for (int indice = 1 ; indice <= numar_cuvinte ; indice++)
        { cout << locatie[indice] -> termen << '\n'; }

    cout.close(); cin.close();
    return 0;
}