Cod sursa(job #96752)

Utilizator astronomyAirinei Adrian astronomy Data 3 noiembrie 2007 12:23:22
Problema Abc2 Scor Ascuns
Compilator c Status done
Runda Marime 0.95 kb
#include <stdio.h>
#include <string.h>

#define MOD (1<<24)-1
#define base 3

char ok[1<<24], sir[10000100];
int res, L, N, put;

void read_and_solve(void)
{
    int i, j, k, val;
    char aux[32];

    scanf("%s\n", &sir), N = strlen(sir);

    while( !feof(stdin) )
    {
        scanf("%s\n", &aux);
        if(!L) L = strlen(aux);
        for(val = 0, i = 0; i < L; i++)
            val = (val*base+(aux[i]-'a')) & MOD;
        ok[val] = 1;
    }

    for(put = 1, i = 1; i <= L; i++)
        put = (put*base) & MOD;
    
    for(val = 0, i = 0; i < N; i++)
    {
        val = (val*base+(sir[i]-'a')) & MOD;
        if(i >= L)
            val = (val-(put*(sir[i-L]-'a'))&MOD+MOD+1)&MOD;
        if(i >= L-1 && ok[val])
            res++;
    }

    printf("%d\n", res);
}

int main(void)
{
    freopen("abc2.in", "rt", stdin);
    freopen("abc2.out", "wt", stdout);

    read_and_solve();

    return 0;
}