Cod sursa(job #111716)

Utilizator sealTudose Vlad seal Data 1 decembrie 2007 18:50:42
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include<stdio.h>
#define Tm 10000001
#define Nm 1000000
#define Sigma 3
#define Wm 21
char T[Tm],Match[Nm];
int Q[Nm],Trie[Nm][Sigma],D[Nm][Sigma],Fail[Nm],n,ans;

void read_and_insert()
{
    char W[Wm];
    int i,q;
    
    freopen("abc2.in","r",stdin);
    gets(T);
    while(scanf("%s",W)==1)
    {
        for(q=i=0;W[i];++i)
        {
            if(!Trie[q][W[i]-'a'])
                Trie[q][W[i]-'a']=++n;
            q=Trie[q][W[i]-'a'];
        }
        Match[q]=1;
    }
}

void construct_automaton()
{
    int l,r,x,i,y,q,j;

    Q[l=r=0]=0;
    for(i=0;i<Sigma;++i)
        if(Trie[0][i])
            D[0][i]=Trie[0][i];
        else
            D[0][i]=0;
    while(l<=r)
    {
        x=Q[l++];
        if(Match[Fail[x]])
            Match[x]=1;
        for(i=0;i<Sigma;++i)
        {
            y=Trie[x][i];
            if(!y)
                continue;

            Q[++r]=y;
            q=Fail[x];
            while(q && !Trie[q][i])
                q=Fail[q];
            if(Trie[q][i] && Trie[q][i]!=y)
                Fail[y]=Trie[q][i];
            else
                Fail[y]=0;

            for(j=0;j<Sigma;++j)
                if(Trie[y][j])
                    D[y][j]=Trie[y][j];
                else
                    D[y][j]=D[Fail[y]][j];
        }
    }
}

void match()
{
    int i,q;

    for(q=i=0;T[i];++i)
    {
        q=D[q][T[i]-'a'];
        ans+=Match[q];
    }
}

void write()
{
    freopen("abc2.out","w",stdout);
    printf("%d\n",ans);
}

int main()
{
    read_and_insert();
    construct_automaton();
    match();
    write();
    return 0;
}