Cod sursa(job #1967282)

Utilizator Burbon13Burbon13 Burbon13 Data 16 aprilie 2017 13:13:26
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.19 kb
#include <cstdio>
#include <queue>
#include <cctype>
#include <cstring>

using namespace std;

struct Nod
{
    int nr;
    Nod *urm[26], *fail;
    vector <int> cv;

    Nod()
    {
        nr = 0;
        for(int i = 0; i < 26; ++i)
            urm[i] = 0;
        fail = 0;
    }
} *t, *q[10005*10005];

char s[1000002], aux[10002];
int nr,nrq, ans[102];

void inserare(char *p, Nod *n, int nr)
{
    if(not isalpha(*p))
    {
        n->cv.push_back(nr);
        return;
    }

    int lit = *p - 'a';
    if(n->urm[lit] == 0)
        n->urm[lit] = new Nod;
    inserare(p+1,n->urm[lit],nr);
}

void citire()
{
    scanf("%s", s);
    scanf("%d", &nr);

    for(int i = 1; i <= nr; ++i)
    {
        scanf("%s", aux);
        ///printf("%s\n", aux);
        inserare(aux,t,i);
    }
}

void bfs()
{
    t->fail = t;
    q[nrq++] = t;
    for(int i = 0; i < nrq; ++i)
    {
        Nod *nod = q[i];
        for(int lit = 0; lit < 26; ++lit)
            if(nod->urm[lit])
            {
                Nod *fl = nod->fail;

                while(fl != t && fl->urm[lit] == 0)
                    fl = fl->fail;

                if(fl->urm[lit] && fl->urm[lit] != nod->urm[lit])
                    fl = fl->urm[lit];

                nod->urm[lit]->fail = fl;
                q[nrq++] = nod->urm[lit];
            }
    }
}

void potrivire()
{
    int ln = strlen(s);
    Nod *ps = t;
    for(int i = 0; i < ln; ++i)
    {
        int lit = (int)s[i] - 'a';
        while(ps != t && ps->urm[lit] == 0)
            ps = ps->fail;
        if(ps->urm[lit])
            ps = ps->urm[lit];
        ps->nr ++;
    }
}

void suma()
{
    for(int i = nrq - 1; i >= 0; --i)
    {
        q[i]->fail->nr += q[i]->nr;

        for(vector<int>::iterator it = q[i]->cv.begin(); it != q[i]->cv.end(); ++it)
            ans[*it] += q[i]->nr;
    }
}

void afish()
{
    for(int i = 1; i <= nr; ++i)
        printf("%d\n", ans[i]);
}

int main()
{
    freopen("ahocorasick.in", "r", stdin);
    freopen("ahocorasick.out", "w", stdout);
    t = new Nod;
    citire();
    bfs();
    potrivire();
    suma();
    afish();
    return 0;
}