Cod sursa(job #831393)

Utilizator geniucosOncescu Costin geniucos Data 8 decembrie 2012 16:28:34
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include<cstdio>
#include<cstring>
using namespace std;
int i,j,l,n,nr,l1[109];
char sir[1000004],s[109][10009];
struct nod
{
    int ap;
    nod *urm[26];
    nod *phi;
    nod()
    {
        memset(urm,0,sizeof(urm));
        phi=0;
        ap=0;
    }
};
nod *aux,*t,*p,*q[1000004];
int main()
{
freopen("ahocorasick.in","r",stdin);
freopen("ahocorasick.out","w",stdout);
gets(sir+1);
l=strlen(sir+1);
scanf("%d\n",&n);
t=new nod;
for(i=1;i<=n;i++)
{
    gets(s[i]+1);
    l1[i]=strlen(s[i]+1);
    p=t;
    for(j=1;j<=l1[i];j++)
    {
        if(p->urm[s[i][j]-'a']==0) p->urm[s[i][j]-'a']=new nod;
        p=p->urm[s[i][j]-'a'];
    }
}
//////////////////////////////bf si phi-ul
t->phi=t;
nr=0;
for(i=0;i<26;i++)
    if(t->urm[i]!=0)
    {
        nr++;
        q[nr]=t->urm[i];
        q[nr]->phi=t;
    }
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!=t&&aux->urm[j]==0)
                aux=aux->phi;
            if(aux->urm[j]!=0) aux=aux->urm[j];
            q[nr]->phi=aux;
        }
/////////////////////////////calculez
aux=t;
for(i=1;i<=l;i++)
{
    while(aux!=t&&aux->urm[sir[i]-'a']==0)
        aux=aux->phi;
    if(aux->urm[sir[i]-'a']!=0)
        aux=aux->urm[sir[i]-'a'];
    aux->ap++;
}
for(i=nr;i>=1;i--)
    q[i]->phi->ap+=q[i]->ap;
////////////////////////////afisez
for(i=1;i<=n;i++)
{
    p=t;
    for(j=1;j<=l1[i];j++)
        p=p->urm[s[i][j]-'a'];
    printf("%d\n",p->ap);
}
return 0;
}