Cod sursa(job #111616)

Utilizator sealTudose Vlad seal Data 1 decembrie 2007 15:55:45
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 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],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=0,r=-1,x,i,y,q;

    for(i=0;i<Sigma;++i)
    {
        y=Trie[i][0];
        if(!y)
            continue;
        Q[++r]=y;
        Fail[y]=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])
                Fail[y]=Trie[i][q];
            else
                Fail[y]=0;
        }
    }
}

void match()
{
    int i,q;

    for(q=i=0;T[i];++i)
    {
        while(q && !Trie[T[i]-'a'][q])
            q=Fail[q];
        if(Trie[T[i]-'a'][q])
            q=Trie[T[i]-'a'][q];
        else
            q=0;
        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;
}