Cod sursa(job #1574186)

Utilizator binicBinica Nicolae binic Data 20 ianuarie 2016 11:53:28
Problema Aho-Corasick Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include<cstdio>
#include<cstring>
using namespace std;
int i,j,n,nr,m[104];
char s[1000004],sir[103][10003];
struct trie
{
    int val;
    trie *urm[26];
    trie *phi;
    trie()
    {
        val=0;
        phi=0;
        memset(urm,0,sizeof(urm));
    }
}*r,*p,*aux,*q[1000004];
int main()
{
    freopen("ahocorasick.in","r",stdin);
    freopen("ahocorasick.out","w",stdout);
    gets(s);
    m[0]=strlen(s);
    scanf("%d\n",&n);
    r=new trie;
    for( i=1;i<=n;i++)
    {
        gets(sir[i]);
        m[i]=strlen(sir[i]);
        p=r;
        for( j=0;j<m[i];j++)
        {
            if(p->urm[sir[i][j]-'a']==0)    p->urm[sir[i][j]-'a']=new trie;
            p=p->urm[sir[i][j]-'a'];
        }
    }

    r->phi=r;
    nr=0;
    for( i=0;i<26;i++)
        if(r->urm[i]!=0)
        {
            nr++;
            q[nr]=r->urm[i];
            q[nr]->phi=r;
        }

    for( i=1;i<=nr;i++)
    {
        for( j=0;j<26;j++)
            if(q[i]->urm[j]!=0)
            {
                nr++;
                q[nr]=q[i]->urm[j];
                aux=q[i]->phi;

                while(aux!=r&&aux->urm[j]==0)
                    aux=aux->phi;

                if(aux->urm!=0)aux=aux->urm[j];
                q[nr]->phi=aux;
            }
    }
    aux=r;
    for( i=0;i<m[0];i++)
    {
        while(aux!=r&&aux->urm[s[i]-'a']==0)
            aux=aux->phi;
        if(aux->urm[s[i]-'a']!=0)
            aux=aux->urm[s[i]-'a'];
        aux->val++;
    }
    for( i=nr;i>=1;i--)
        q[i]->phi->val+=q[i]->val;
    for( i=1;i<=n;i++)
    {
        aux=r;
        for( j=0;j<m[i];j++)
            aux=aux->urm[sir[i][j]-'a'];
        printf("%d\n",aux->val);
    }
    return 0;
}