Cod sursa(job #501257)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 14 noiembrie 2010 17:27:55
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 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,nr,poww,MOD2,HA2,HB2,poww2;
char A[2000100],B[2000100],sir[2000100];
long long HA,HB;

int main () {
	
	fscanf(f,"%s %s",A,B); N = strlen(A); M = strlen(B);
	MOD = 100007; MOD2 = 100021;
	
	bz = 73;
	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;
	}
	for ( i = 0 ; i < N - 1 ; ++i ){
		poww = ( poww * bz ) % MOD;
		poww2 = ( poww2 * bz ) % MOD2;
	}
	
	if ( N > M ){
		fprintf(g,"0\n");
		return 0;
	}
	if ( HA == HB && HA2 == HB2){
		++nr;
		sir[0] = 1;
	}
	
	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;
		
		
		if ( HA == HB && HA2 == HB2){
			++nr;
			sir[ i - N + 1] = 1;
		}
		
		
	}
	fprintf(g,"%d\n",nr); nr = 0;
	
	for ( i = 0 ; i < M && nr < 1000 ; ++i ){
		if ( sir[i] ){
			fprintf(g,"%d ",i);
			++nr;
		}
		
	}
	
	fclose(f);
	fclose(g);
	
	return 0;	
	
}