Cod sursa(job #527043)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 30 ianuarie 2011 15:01:59
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<stdio.h>
#include<string>
#define MOD1 6379
#define MOD2 6449
#define B 73

FILE*f=fopen("abc2.in","r");
FILE*g=fopen("abc2.out","w");

int i,j,H1,H2,Lc,hsh1,hsh2,Rez,N,p1,p2;
char E[6500][6500],A[10000010],C[25];

int main () {
	
	fscanf(f,"%s\n",A);
	
	fgets(C+1,22,f);
	for ( i = 1 ; C[i] >= 'a' && C[i] <= 'z' ; ++i );
	--i;
	Lc = i;
	for ( i = 1 ; i <= Lc ; ++i ){
		H1 = ( ( H1 * B ) + C[i] ) % MOD1;
		H2 = ( ( H2 * B ) + C[i] ) % MOD2;
	}
	
	E[H1][H2] = 1;
	
	while ( fgets(C+1,22,f) ) {
		
		H1 = H2 = 0;
		
		for ( i = 1 ; i <= Lc ; ++i ){
			H1 = ( ( H1 * B ) + C[i] ) % MOD1;
			H2 = ( ( H2 * B ) + C[i] ) % MOD2;
		}
		E[H1][H2] = 1;
	}
	
	p1 = p2 = 1;
	for ( i = 1 ; i < Lc ; ++i ){
		p1 = ( p1 * B ) % MOD1;
		p2 = ( p2 * B ) % MOD2;
	}
	
	for ( i = 0 ; i < Lc ; ++i ){
		hsh1 = ( ( hsh1 * B ) + A[i] ) % MOD1;
		hsh2 = ( ( hsh2 * B ) + A[i] ) % MOD2;
	}
	N = strlen(A);
	
	if ( E[hsh1][hsh2] )
		++Rez;
	
	for ( i = Lc ; i < N ; ++i ){
		hsh1 =   (( hsh1 - (A[ i - Lc] * p1) % MOD1 + MOD1 ) * B + A[i] ) % MOD1;
		hsh2 =   (( hsh2 - (A[ i - Lc] * p2) % MOD2 + MOD2 ) * B + A[i] ) % MOD2;
		if ( E[hsh1][hsh2] )
			++Rez;
	}
	
	fprintf(g,"%d\n",Rez);
	
	fclose(f);
	fclose(g);
	
	return 0;
}