Cod sursa(job #501239)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 14 noiembrie 2010 17:10:23
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include<stdio.h>
#include<string>

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

int N,M,hash[257],i,k,MOD,bz,sir[1001],nr,poww,MOD2,HA2,HB2,poww2;
char A[2000100],B[2000100];
long long HA,HB;

int main () {
	
	fscanf(f,"%s%s",A,B); N = strlen(A); M = strlen(B);
	MOD = 100020; MOD2 = 110009;
	/*k = -1 ;
	for ( i = 0 ; i <= 9 ; ++i )
		hash[ i + '0' ] = ++k;
	for ( i = 'A' ; i <= 'Z' ; ++i )
		hash[i] = ++k;
	for ( i = 'a' ; i <= 'z' ; ++i )
		hash[i] = ++k;
	*/
	//baza 64
	bz = 257;
	poww = poww2 = 1;
	for ( i = 0 ; i < N ; ++i ){
		HA = ( HA * bz + A[i] ) % MOD;
		HB = ( HB * bz + B[i] ) % MOD;
		HA2 = ( HA2 * bz + A[i] ) % MOD2;
		HB2 = ( HB2 * bz + B[i] ) % MOD2;
		if ( i != N - 1 ){
			poww = ( poww * bz ) % MOD;
			poww2 = ( poww2 * bz ) % MOD2;
		}
	}
	
	if ( N > M ){
		fprintf(g,"0\n");
		return 0;
	}
	if ( HA == HB && HA2 == HB2){
		sir[++nr] = 0;
	}
	
	for ( i = N ; i < M ; ++i ){
		
		HB = ((HB - (B[i - N] * poww) % MOD + MOD) * bz + B[i] ) % MOD;
		HB2 = ((HB2 - (B[i - N] * poww2) % MOD2 + MOD2) * bz + B[i]) % MOD2;
		/*
		HB -= ( hash[B[i-N]] * poww) % MOD ;
		HB = ( HB * bz + hash[B[i]] ) ;
		if ( HB > MOD )
			HB -= MOD;
		
		HB2 -= ( hash[B[i-N]] * poww2) % MOD2 ;
		HB2 = ( HB2 * bz + hash[B[i]] ) ;
		if ( HB2 > MOD2 )
			HB2 -= MOD2;
		*/
		if ( HA == HB && HA2 == HB2){
			++nr;
			if ( nr < 1000 )
				sir[nr] = i - N + 1;
		}
		
		
	}
	
	fprintf(g,"%d\n",nr);
	for ( i = 1 ; i <= nr ; ++i )
		fprintf(g,"%d ",sir[i]);
	
	fclose(f);
	fclose(g);
	
	return 0;	
	
}