Cod sursa(job #1683812)

Utilizator BugirosRobert Bugiros Data 10 aprilie 2016 16:42:56
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.65 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 1000005;

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

struct nod_corasick
{
    static const int SIGMA = 'z' - 'a' + 1;

    vector<int> siruri;//sirurile care se termina in nodul curent
    int nr_potriviri;//numarul de potriviri din nodul curent sau din fii lui
    nod_corasick *fii[SIGMA];
    nod_corasick *intoarcere;

    nod_corasick()
    {
        nr_potriviri = 0;
        intoarcere = NULL;
        memset(fii, 0, sizeof(fii));
    }

    void inserare(char *s, int id)
    {
        if (*s == 0)
        {
            siruri.push_back(id);
            return;
        }
        int idc = *s - 'a';
        if (fii[idc] == 0)
            fii[idc] = new nod_corasick;
        fii[idc] -> inserare(s + 1, id);
    }
};

const int MAXCUVANT = 10005;

nod_corasick *coada[MAXCUVANT * MAXCUVANT];
int pcoada,qcoada;


struct corasick
{
    static const int NRCUVINTE = 105;
    static const int SIGMA = 'z' - 'a' + 1;

    nod_corasick *radacina;
    int nrcuv;


    int raspuns[NRCUVINTE];



    corasick()
    {
        radacina = new nod_corasick;
        nrcuv = 0;
        //memset(coada, 0, sizeof(coada));
        pcoada = 1;
        qcoada = 0;
        memset(raspuns, 0, sizeof(raspuns));
    }

    void adaugare_cuvant(char *s)
    {
        ++nrcuv;
        radacina -> inserare(s, nrcuv);
    }

    void bfs()
    {
        nod_corasick *pred;//unde o sa indice intoarcere fiecarui nod
        radacina -> intoarcere = radacina;
        pcoada = 1;
        qcoada = 1;
        coada[1] = radacina;
        while (pcoada <= qcoada)
        {
            nod_corasick *nod = coada[pcoada];
            ++pcoada;
            for (int i = 0;i < SIGMA;++i)
                if (nod -> fii[i] != NULL)
                {
                    for (pred = nod -> intoarcere; pred != radacina && pred -> fii[i] == NULL; pred = pred -> intoarcere)
                        ;
                    if (pred -> fii[i] != NULL && pred -> fii[i] != nod -> fii[i])
                        pred = pred -> fii[i];
                    nod -> fii[i] -> intoarcere = pred;
                    coada[++qcoada] = nod -> fii[i];
                }
        }
        radacina -> intoarcere = NULL;
    }

    void antibfs()
    {
        for (int i = qcoada;i > 0;--i)
        {
            nod_corasick *nod = coada[i];
            if(nod -> intoarcere != NULL)
                nod -> intoarcere -> nr_potriviri += nod -> nr_potriviri;
            for (unsigned int j = 0;j < nod -> siruri.size();++j)
                raspuns[nod -> siruri[j]] = nod -> nr_potriviri;
        }
    }

    void gestionare_sir(char *s)
    {
        nod_corasick *p = radacina;
        for (int i = 0;s[i]  != 0;++i)
        {
            int urm = s[i] - 'a';
            //cautam o muchie pe care sa putem merge in jos
            while(p -> fii[urm] == NULL && p != radacina)
                p = p -> intoarcere;
            if (p -> fii[urm] != NULL)
                p = p -> fii[urm];
            ++(p -> nr_potriviri);
        }
        antibfs();
    }
};


corasick *cora;

int main()
{
    cora = new corasick;
    char *sir = new char[MAXN];
    int n;
    char cuv[MAXCUVANT];
    in >> sir;
    in >> n;
    for (int i = 1;i <= n;++i)
    {
        //memset(cuv, 0, sizeof(cuv));
        in >> cuv;
        cora -> adaugare_cuvant(cuv);
    }
    cora -> bfs();
    cora -> gestionare_sir(sir);
    for (int i = 1;i <= n;++i)
        out << cora -> raspuns[i] << '\n';
    return 0;
}