Cod sursa(job #2417225)

Utilizator GoogalAbabei Daniel Googal Data 29 aprilie 2019 11:34:52
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.06 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m, nr;

int p[101];
int val[101];

char a[1000005];
char s[10005];

struct nod
{
    int k,val;
    nod *urm[26],*ant;

    nod()
    {
        val=0;
        k=0;
        memset(urm,0,sizeof(urm));
    }
}*o;

deque <nod*> q, q2;

void add(int k)
{
    int i;
    nod *x=o;
    for (i=0; i<n; i++)
    {
        if (x->urm[s[i]-'a']==0)
            x->urm[s[i]-'a']=new nod;
        x=x->urm[s[i]-'a'];
    }
    if (x->k==0)
        x->k=k;
    p[k]=x->k;
}

void bf()
{
    int i;
    nod *x,*y;
    for (i=0; i<26; i++)
        if (o->urm[i])
        {
            o->urm[i]->ant=o;
            q2.push_back(o->urm[i]);
        }
    while (!q2. empty())
    {
        x=q2.front();
        q2.pop_front();
        q.push_back(x);
        for (i=0; i<26; i++)
            if (x->urm[i])
            {
                y=x->ant;
                while (y!=o && !y->urm[i])
                    y=y->ant;
                if (y->urm[i])
                    x->urm[i]->ant=y->urm[i];
                else
                    x->urm[i]->ant=o;
                q2.push_back(x->urm[i]);
            }
    }
}

void potrivire()
{
    int i;
    nod *x=o;
    for (i=0; i<m; i++)
    {
        while (x!=o && !x->urm[a[i]-'a'])
            x=x->ant;
        if (x->urm[a[i]-'a'])
            x=x->urm[a[i]-'a'];
        x->val++;
    }
}

void solve()
{
    nod *x;
    while (!q.empty())
    {
        x=q.back();
        q.pop_back();
        x->ant->val+=x->val;
        if (!val[x->k])
            val[x->k]=x->val;
    }
}

int main()
{
    int i;
    o = new nod;

    in >> a >> nr;

    m = strlen(a);

    for (i=1; i<=nr; i++)
    {
        in>>s;
        n=strlen(s);
        add(i);
    }

    o->ant=0;

    bf();
    potrivire();
    solve();

    for (i=1; i<=nr; i++)
        out<<val[p[i]]<<'\n';

    in.close();
    out.close();

    return 0;
}