Cod sursa(job #1198657)

Utilizator alex_bucevschiBucevschi Alexandru alex_bucevschi Data 16 iunie 2014 16:13:43
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 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;
}