Cod sursa(job #500669)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 12 noiembrie 2010 19:12:41
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 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;
char A[2000100],B[2000100];
long long HA,HB;

int main () {
	
	fscanf(f,"%s%s",A,B); N = strlen(A); M = strlen(B);
	MOD = 1 << 29;
	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 = 64;
	poww = 1;
	for ( i = 0 ; i < N ; ++i ){
		HA = ( HA * bz + hash[A[i]] ) % MOD;
		HB = ( HB * bz + hash[B[i]] ) % MOD;
		if ( i != N - 1 )
			poww = (poww * bz) % MOD;
	}
	
	if ( N > M ){
		fprintf(g,"0\n");
		return 0;
	}
	if ( HA == HB ){
		sir[++nr] = 0;
	}
	
	for ( i = N ; i <= M ; ++i ){
		
		HB -= ( hash[B[i-N]] * poww) % MOD ;
		HB = ( HB * bz + hash[B[i]] ) % MOD;
		
		if ( HA == HB ){
			++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;	
	
}