Cod sursa(job #98424)

Utilizator ZeusCatalin Tiseanu Zeus Data 10 noiembrie 2007 13:20:25
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 2.37 kb

#include <cstdio>
#include <cstring>

#define H_SIZE 4789327
#define NR_H 4

int N, M, L, ret, at[NR_H], ok;
char A[10111111], cuv[50111][22];

unsigned short hash[NR_H][H_SIZE];
int base[NR_H] = { 101, 207, 413, 593 }, po[NR_H][22];

int main()
{
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);
    
    int i, j, l, k;
    
    gets( A );
    L = strlen( A );
    
    while( gets( cuv[++N] ) );
    --N;
    
    if( N == 0 )
    {
        printf("0\n");
        return 0;    
    }
    
    M = strlen(cuv[1]);
    
    if( M > L )
    {
        printf("0\n");
        return 0;   
    } 

    for( l = 0; l < L; l++ ) A[l] -= 'a';
    for( i = 1; i <= N; i++ )    
         for( l = 0; l < M; l++ ) cuv[i][l] -= 'a';
    
    for( j = 0; j < NR_H; j++ )
    {
         po[j][0] = 1;
         
         for( i = 1; i <= M; i++ )
              po[j][i] = ( (long long)( po[j][i-1] ) * base[j] ) % H_SIZE;    
    }
    
    for( i = 1; i <= N; i++ )
         for( j = 0; j < NR_H; j++ )
         {
              int val = 0;  
              
              for( k = 0; k < M; k++ )
                   val += po[j][M-k-1] * (int)cuv[i][k],
                   val %= H_SIZE;
                   
              hash[ j ][ val ] = i;   
         } 
       
    for( l = 0; l < L; l++ )
    {
         for( j = 0; j < NR_H; j++ )     
         {
              if( l < M ) at[j] += po[j][M-l-1] * (int)A[l], at[j] %= H_SIZE;
              else
              {
//                    printf("%d: %d %d %d %d\n", j, at[j], po[j][M-1], (int)A[l-M], (int)A[l] );
                  
                    at[j] = ( base[j] * ( (at[j] - po[j][M-1] * (int)(A[ l - M ]) + 10 * H_SIZE ) % H_SIZE ) ) % H_SIZE + (int)(A[l]),
                    at[j] %= H_SIZE;    
              }
         }
/*         
         printf("%d :\n", l );
         for( i = 0; i < NR_H; ++i )
              printf("%d ", at[i] ); printf("\n");
*/         
         if( l >= M - 1 )
         {
              ok = 1;
              
              for( i = 0; ok && i < NR_H; i++ )
                   if( !hash[ i ][ at[i] ] || hash[ i ][ at[i] ] != hash[ 0 ][ at[0] ] )
                       ok = 0;   
         
              if( ok )
                  ret++;           
         }
    }
    
    printf("%d\n", ret);
    
    return 0;    
}