Cod sursa(job #524894)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 23 ianuarie 2011 15:49:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include<stdio.h>
#include<stdlib.h>
#include<string>

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

int N,M,sir[1005],Nr,bz,i;
unsigned int HA1,HB1,P1;
unsigned char HA2,HB2,P2;
char A[2000005],B[2000005];

int main () {
	fscanf(f,"%s",A);
	fscanf(f,"%s",B);
	N = strlen(A); M = strlen(B); bz = 73;
	if ( N > M ){
		fprintf(g,"%d\n",0);
		fclose(f); fclose(g); exit(0);
	}
	for ( i = 0 ; i < N ; ++i ){
		HA1 = HA1 * bz + A[i];
		HA2 = HA2 * bz + A[i];
		HB1 = HB1 * bz + B[i];
		HB2 = HB2 * bz + B[i];
	}
	P1 = P2 = 1;
	for ( i = 1 ; i < N ; ++i ){
		P1 = P1 * bz ;
		P2 = P2 * bz ;
	}
	if ( HA1 == HB1 && HA2 == HB2 ){
		sir[++Nr] = 0;
	}
	
	for ( i = N ; i < M ; ++i ){
		HB1 = HB1 - B[ i - N ] * P1;
		HB1 = HB1 * bz + B[i];
		HB2 = HB2 - B[ i - N ] * P2;
		HB2 = HB2 * bz + B[i];
		if ( HA1 == HB1 && 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;
}