Cod sursa(job #1198625)

Utilizator alex_bucevschiBucevschi Alexandru alex_bucevschi Data 16 iunie 2014 14:08:05
Problema Aho-Corasick Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 3.75 kb
#include <cstdio>
#include <cstring>

using namespace std;
struct nod
{
    nod *s[26],*fail;
    int cnt;
    char S[26];
    nod()
    {
        for(int i=0;i<26;i++)
            s[i]=0;
        fail=0;
        cnt=0;
        memset(S,0,sizeof(S));
    }
};
nod *root,*pt,*poz[110],*Q[1000010];
char A[1000010],B[10010],*p;
int n,i,t,b;
int main()
{
    freopen("ahocorasick.in","r",stdin);
    freopen("ahocorasick.out","w",stdout);
    scanf("%s",A);
    scanf("%d",&n);
    root=new nod;
    for(i=1;i<=n;i++)
    {
        scanf("%s",B);
        for(pt=root,p=B;*p;p++)
        {
            if(!pt->s[*p-'a'])pt->s[*p-'a']=new nod;
            int LG=strlen(pt->S);
            pt->S[LG]=*p;
            pt=pt->s[*p-'a'];
        }
        poz[i]=pt;
    }
    root->fail=root;
    for(p=root->S;*p;p++)
    {
        Q[++t]=root->s[*p-'a'];
        Q[t]->fail=root;
    }
    for(b=1;b<=t;b++)
    {
        for(p=Q[b]->S;*p;p++)
        {
            for(pt=Q[b]->fail;;pt=pt->fail)
            {
                if(pt->s[*p-'a'])
                {
                    Q[b]->s[*p-'a']->fail=pt->s[*p-'a'];
                    break;
                }
                if(pt==root)
                {
                    Q[b]->s[*p-'a']->fail=root;break;
                }
            }
            Q[++t]=Q[b]->s[*p-'a'];
        }
    }
    for(p=A,pt=root;*p;)
    {
        if(pt->s[*p-'a']){pt=pt->s[*p-'a'];pt->cnt++;p++;continue;}
        if(pt==root){p++;continue;}
        pt=pt->fail;
    }
    for(;t;t--)
        Q[t]->fail->cnt+=Q[t]->cnt;
    for(i=1;i<=n;i++)
        printf("%d\n",poz[i]->cnt);
    return 0;
}

//#include<cstdio>
//#define I U->inf
//using namespace std;
//struct lst
//{
//    int inf;
//    lst *urm;
//    lst()
//    {
//        inf=0;
//        urm=0;
//    }
//};
//struct nod
//{
//    lst *L;
//    int A;
//    nod *S[26],
//    *F;
//    nod(){L=0;A=0;for(int i=0;i<26;i++)S[i]=0;F=0;}};
//nod *R,*poz[110],*Q[1000000];
//int n,i,b,t;
//char P[1000010],C[10010];
//void read(),solve();
//int main(){read();solve();return 0;}
//void read()
//{
//    char *c;nod *N;
//    lst *NL;
//    int k;R=new nod;
//    freopen("ahocorasick.in","r",stdin);freopen("ahocorasick.out","w",stdout);
//    scanf("%s",P);scanf("%d",&n);
//    for(i=1;i<=n;i++)
//    {
//        scanf("%s",C);
//        for(c=C,N=R;*c;c++)
//        {
//            k=*c-'a';
//            if(!N->S[k])
//            {
//                N->S[k]=new nod;
//                NL=new lst;
//                NL->inf=k;
//                NL->urm=N->L;
//                N->L=NL;
//            }
//            N=N->S[k];
//        }
//        poz[i]=N;
//    }
//}
//void solve()
//{
//    nod *N;lst *U;
//    char *c;
//    R->F=R;
//    for(U=R->L;U;U=U->urm)
//    {
//        R->S[I]->F=R;
//        Q[t++]=R->S[I];
//    }
//    for(;b<t;b++)
//    {
//        for(U=Q[b]->L;U;U=U->urm)
//            {
//                for(N=Q[b]->F;;N=N->F)
//                {
//                    if(N->S[I])
//                    {
//                        Q[b]->S[I]->F=N->S[I];break;
//                    }
//                    if(N==R)
//                    {
//                        Q[b]->S[I]->F=R;break;
//                    }
//                }
//                Q[t++]=Q[b]->S[I];
//            }
//    }
//    for(c=P,N=R;*c;)
//    {
//        if(N->S[*c-'a'])
//        {
//            N=N->S[*c-'a'];N->A++;c++;continue;
//        }
//        if(N==R)
//        {
//            c++;continue;
//        }
//        N=N->F;
//    }
//    for(t--;t>=0;t--)
//        Q[t]->F->A+=Q[t]->A;
//    for(i=1;i<=n;i++)
//        printf("%d\n",poz[i]->A);}