Cod sursa(job #661966)

Utilizator proflaurianPanaete Adrian proflaurian Data 15 ianuarie 2012 17:13:03
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include<cstdio>
#include<vector>
#include<deque>
#define LST vector<int>
#define IT vector<int>::iterator it
using namespace std;
struct lst{int inf;lst *urm;lst(){inf=0;urm=0;}};
struct nod
{
    lst *L;
    int ap;
    nod *S[26],*fail;
    nod()
    {
        L=0;
        ap=0;
        for(int i=0;i<26;i++)
            S[i]=0;
        fail=0;
    }
}
;
nod *root,*poz[110],*Q[1000000];
int n,i,Ap,b,t;
char P[1000010],C[10010];
void read(),fail(),upd(nod*,char*),load(),solve();
int main()
{
    read();
    solve();
    return 0;
}
 void solve()
 {
     fail();
     load();
     for(t--;t>=0;t--)Q[t]->fail->ap+=Q[t]->ap;
     for(i=1;i<=n;i++)printf("%d\n",poz[i]->ap);
}
void read()
{
    char *c;nod *N;lst *NL;int k;
    freopen("ahocorasick.in","r",stdin);
    freopen("ahocorasick.out","w",stdout);
    scanf("%s",P);scanf("%d",&n);
    root=new nod;
    for(i=1;i<=n;i++)
    {
        scanf("%s",C);
        for(c=C,N=root;*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 fail()
{
    nod *aux,*faux;lst *laux;
    root->fail=root;
    for(laux=root->L;laux;laux=laux->urm)
    {
        root->S[laux->inf]->fail=root;
        Q[t++]=root->S[laux->inf];
    }
    b=0;
    for(;b<t;)
    {
        aux=Q[b++];
        for(laux=aux->L;laux;laux=laux->urm)
        {
            for(faux=aux->fail;;faux=faux->fail)
            {
                if(faux->S[laux->inf]){aux->S[laux->inf]->fail=faux->S[laux->inf];break;}
                if(faux==root){aux->S[laux->inf]->fail=root;      break;}
            }
            Q[t++]=aux->S[laux->inf];
        }
    }
}
void load()
{
    nod *N;char *c;
    for(c=P,N=root;*c;)
    {
        if(N->S[*c-'a']){N=N->S[*c-'a'];N->ap++;c++;continue;}
        if(N==root){c++;continue;}
        N=N->fail;
    }

}