Cod sursa(job #1552208)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 17 decembrie 2015 14:02:23
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.2 kb
#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;
struct nod
{
    nod * po[30];
    nod * fail,*tata;
    int nrc,ans;
    short int ch;
    nod()
    {
        nrc=ans=0;ch=-1;
        fail=tata=NULL;
        for(int i=0;i<=26;i++)
            po[i]=NULL;
    };
};
char si[1000005],s2[10005];
int st,dr;
nod * root,* dq[1000000],*loc[105];
void bfs(nod * rad)
{
    nod * tm;
    int i;
    st=dr=1;dq[1]=rad;
    while(st<=dr)
    {
        rad=dq[st];
    if(rad!=root)
    {
        tm=rad->tata->fail;
        while(tm!=NULL)
        {
            if(tm->po[rad->ch]!=NULL)
            {
                rad->fail=tm->po[rad->ch];
            break;
            }
            else
            {
                tm=tm->fail;
            }
        }
        if(tm==NULL)
            rad->fail=root;
            rad->nrc+=rad->fail->nrc;
    }
    for(i=0;i<=26;i++)
        if(rad->po[i]!=NULL)
        {
        dr++;
        dq[dr]=rad->po[i];
        }
        st++;
    }
}
int main()
{
    freopen("ahocorasick.in","r",stdin);
    freopen("ahocorasick.out","w",stdout);
    int n,i,j,l,ans=0;
    nod * tm;
    root=new nod();
    gets(si+1);
    scanf("%d\n",&n);
    for(i=1;i<=n;i++)
    {
        gets(s2+1);
        l=strlen(s2+1);
        tm=root;
        for(j=1;j<=l;j++)
        {
            s2[j]-='a';
            if(tm->po[s2[j]]==NULL)
            {
                tm->po[s2[j]]=new nod();
                tm->po[s2[j]]->tata=tm;
                tm->po[s2[j]]->ch=s2[j];
            }
            tm=tm->po[s2[j]];
        }
        loc[i]=tm;
        tm->nrc++;
    }
    bfs(root);
    tm=root;
    l=strlen(si+1);
    for(i=1;i<=l;i++)
    {
        si[i]=si[i]-'a';
        while(tm->po[si[i]]==NULL && tm!=root)
        {
            tm=tm->fail;
        }
            if(tm->po[si[i]]!=NULL)
            {
        tm=tm->po[si[i]];
        if(tm->nrc>0)
        tm->ans++;
            }

    }
        for(i=dr;i>=1;i--)
            if(dq[i]->fail!=NULL)
        {
            dq[i]->fail->ans+=dq[i]->ans;
        }
    for(i=1;i<=n;i++)
    printf("%d\n",loc[i]->ans);
    return 0;
}