Cod sursa(job #1558176)

Utilizator delia_99Delia Draghici delia_99 Data 28 decembrie 2015 19:53:58
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include <cstdio>
#include <cstring>
#define E 'z'-'a'
#define NMAX 1000000
#define SMAX 10000

using namespace std;

struct Trie
{
    int nr;
    Trie *son[E+5],*phi;
    Trie()
    {
        phi=NULL;
        nr=0;
        for(int i=0; i<=E; ++i)
            son[i]=NULL;
    }
};

char A[NMAX+10],s[SMAX+10];
int n,i,crt,lst;
Trie *T,*v[1000010],*sol[110];


Trie *upd(Trie *B,char *s,int l)
{
    int c;
    if(l==0)
        return B;
    c=*s-'a';
    if(B->son[c]==NULL)
        B->son[c]=new Trie;
    upd(B->son[c],s+1,l-1);
}

void findphi()
{
    Trie *B,*node;
    T->phi=T;
    v[++lst]=T;
    crt=1;
    while(crt<=lst)
    {

        node=v[crt];
        for(i=0; i<=E; ++i)
            if(node->son[i]!=NULL)
            {
                B=node;
                if(B!=T)
                {
                    B=B->phi;
                    while(B!=T && B->son[i]==NULL)
                        B=B->phi;
                    if(B->son[i]!=NULL)
                        B=B->son[i];
                    v[crt]->son[i]->phi=B;
                }
                else B->son[i]->phi=T;
                v[++lst]=v[crt]->son[i];
            }
        ++crt;
    }
}

void findnr()
{
    int l,c;
    l=strlen(A);
    Trie *B;
    B=T;
    for(int i=0; i<l; ++i)
    {
        c=A[i]-'a';
        while(B!=T && B->son[c]==NULL)
            B=B->phi;
        if(B->son[c]!=NULL)
            B=B->son[c];
        ++B->nr;
    }
    for(int i=lst; i; --i)
        v[i]->phi->nr+=v[i]->nr;
}

int main()
{
    freopen("ahocorasick.in","r",stdin);
    freopen("ahocorasick.out","w",stdout);
    T=new Trie;
    gets(A);
    scanf("%d\n",&n);
    for(i=1; i<=n; ++i)
    {
        gets(s);
        sol[i]=upd(T,s,strlen(s));
    }
    findphi();
    findnr();
    for(i=1; i<=n; ++i)
        printf("%d\n",sol[i]->nr);
    return 0;
}