Cod sursa(job #96768)

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

#define MOD (1<<28)-1
#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, 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 = v2 = 0, i = 0; i < L; i++)
            v1 = (v1*base+(aux[i]-'a')) & ((1<<24)-1),
            v2 = (v2*base+(aux[i]-'a')) & ((1<<23)-1);

        val = (v2*67+v1) & MOD;
            
        baga(val);
    }

    for(put = 1, i = 1; i <= L; i++)
        put = (put*base) & MOD;
    
    for(val = 0, i = 0; i < N; i++)
    {
        v1 = (v1*base+(sir[i]-'a')) & ((1<<24)-1),
        v2 = (v2*base+(sir[i]-'a')) & ((1<<23)-1);

        if(i >= L)
            v1 = (v1-(put*(sir[i-L]-'a'))&((1<<24)-1)+(1<<24))&((1<<24)-1),
            v2 = (v2-(put*(sir[i-L]-'a'))&((1<<23)-1)+(1<<23))&((1<<23)-1);

        val = (v2*67+v1) & 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;
}