Cod sursa(job #99131)

Utilizator filipbFilip Cristian Buruiana filipb Data 10 noiembrie 2007 21:43:06
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.83 kb
#include <stdio.h>
#include <string.h>

#define MaxNodes 1000005
#define NMax 10000005

char S[NMax], cuv[25];
int trie[MaxNodes][3], pi[MaxNodes], dep[MaxNodes], nodes;
int q[MaxNodes], cnt;

void make_prefix(void)
{
    int i, c, p, ql, qr;

    for (q[ql=qr=0]=0, pi[0] = -1; qr <= ql; qr++)
        for (c = 0; c < 3; c++)
            if (trie[q[qr]][c] != -1)
            {            
                q[++ql] = trie[q[qr]][c];
                
                for (p = pi[q[qr]]; p >= 0 && trie[p][c] == -1; p = pi[p]);
                
                if (p == -1) pi[q[ql]] = 0;
                else pi[q[ql]] = trie[p][c];                
            }

}

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

    memset(trie, -1, sizeof(trie));
    
    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 = nod = 0; i < L; i++)
            if (trie[nod][cuv[i]-'a'] == -1)
                ++nodes,
                dep[nodes] = dep[nod] + 1,
                trie[nod][cuv[i]-'a'] = nodes,
                nod = nodes;
            else
                nod = trie[nod][cuv[i]-'a'];

    }

    make_prefix();

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

        c = S[i]-'a';
        if (trie[nod][c] != -1)
            nod = trie[nod][c];
        else
        {
            for (; nod >= 0 && trie[nod][c] == -1; nod = pi[nod]);
            
            if (nod == -1) nod = 0;
            else nod = trie[nod][c];
        }

        cnt += (dep[nod] == L);

    }

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

    return 0;
}