Cod sursa(job #104541)

Utilizator filipbFilip Cristian Buruiana filipb Data 16 noiembrie 2007 12:32:57
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.84 kb
#include <stdio.h>
#include <string.h>

#define MaxNodes 1000005
#define NMax 10000005

char S[NMax], cuv[25], F[MaxNodes];
int trie[MaxNodes][3], A[MaxNodes][3], up[MaxNodes], nodes = 1;
int q[MaxNodes], cnt;

void build_automaton(void)
{
    int i, c, ql, qr, x, t;

    for (q[0] = 1, c = 0; c < 3; c++)
    {
        A[1][c] = 1;
        if (trie[1][c])
            q[++ql] = trie[1][c],
            up[q[ql]] = 1;
    }

    for (qr = 1; qr <= ql; qr++)
    {
        x = q[qr];
        for (c = 0; c < 3; c++)
            if (trie[up[x]][c] == x)
                break;
                
        t = A[up[x]][c];
        A[up[x]][c] = x;

        for (c = 0; c < 3; c++)
        {
            if (trie[t][c])
                A[x][c] = trie[t][c];
            else
                A[x][c] = A[t][c];
            
            if (trie[x][c])
                q[++ql] = trie[x][c],
                up[q[ql]] = x;
        }
        
    }
    
}

int main(void)
{
    int i, nod, L = -1, len;
    
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);

    fgets(S, sizeof(S), stdin);
    while (fgets(cuv, sizeof(cuv), stdin) != NULL)
    {
        if (L == -1)
            for (L = 0; cuv[L] >= 'a' && cuv[L] <= 'c'; L++);
        
        for (i = 0, nod = 1; i < L; i++)
        {
            if (cuv[i] < 'a' || cuv[i] >'c') break;
            
            if (!trie[nod][cuv[i]-'a'])
                trie[nod][cuv[i]-'a'] = (++nodes);
            nod = trie[nod][cuv[i]-'a'];
        }
        
        F[nod] = 1;
    }

    build_automaton();

    for (i = 0, nod = 1, len = strlen(S); i < len; ++i)
    {
        if (S[i] < 'a' || S[i] > 'c') break;

        nod = A[nod][S[i]-'a'];
        cnt += (F[nod] == 1);
    }

    printf("%d\n", cnt);

    return 0;
}