Cod sursa(job #96776)

Utilizator astronomyAirinei Adrian astronomy Data 3 noiembrie 2007 13:01:30
Problema Abc2 Scor Ascuns
Compilator c Status done
Runda Marime 1.16 kb
#include <stdio.h>
#include <string.h>

#define MOD 200000033
#define base 3

char T[1<<25], sir[10000100];
int res, L, N, put;

int ok(int val)
{
    if( T[val>>3] & (1<<(val&7)) ) return 1;
    return 0;
}

void baga(int val)
{
    T[val>>3] |= (1<<(val&7));
}


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

    fgets(sir, 1<<24, stdin);
    N = strlen(sir);

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

        baga(v1);
    }

    for(p1 = 1, i = 1; i <= L; i++)
        p1 = (p1*base) % MOD;
        
    for(v1 = 0, i = 0; i < N; i++)
    {
        v1 = (v1*base+(sir[i]-'a')) % MOD;

        if(i >= L)
            v1 = (v1-(p1*(sir[i-L]-'a'))%MOD+MOD) % MOD;
            
        if(i >= L-1 && ok(v1))
            res++;
    }

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

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

    read_and_solve();

    return 0;
}