Cod sursa(job #111720)

Utilizator sealTudose Vlad seal Data 1 decembrie 2007 18:58:20
Problema Abc2 Scor 0
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[Sigma][Nm],D[Sigma][Nm],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[W[i]-'a'][q])
                Trie[W[i]-'a'][q]=++n;
            q=Trie[W[i]-'a'][q];
        }
        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[i][0])
            D[i][0]=Trie[i][0];
        else
            D[i][0]=0;
    while(l<=r)
    {
        x=Q[l++];
        if(Match[Fail[x]])
            Match[x]=1;
        for(i=0;i<Sigma;++i)
        {
            y=Trie[i][x];
            if(!y)
                continue;

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

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

void match()
{
    int i,q;

    for(q=i=0;T[i];++i)
    {
        q=D[T[i]-'a'][q];
        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;
}