Cod sursa(job #147397)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 2 martie 2008 21:08:50
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <cstdio>
#include <cstring>

const long pr1 = 136069;
const long pr2 = 136067;
const long MAX = 2000010;	// TODO : de pus la loc
const long t = 101;

char A[MAX], B[MAX];
long n,m, nr;
long hash1, hash2, test1, test2;
long Save[1002];

bool valid(char a) {
	if ( a>='A' && a<='Z' ) return true;
	if ( a>='0' && a<='9' ) return true;
	return false;
}

bool go_real(long x) {
	return true;
	char c = B[x+n]; B[x+n]=0;
	long r = strcmp(B+x, A);
	B[x+n] = c;
	return r==0;
}

int main() {
	long i;

	freopen("strmatch.in", "r", stdin);
	fgets(A, MAX, stdin);
	fgets(B, MAX, stdin);

	for (n=strlen(A); !valid(A[n]); --n) A[n]=0; ++n;
	for (m=strlen(B); !valid(B[n]); --m) B[n]=0; ++m;

	// calculare hash
	// functie : nr in baza 256 mod un nr prim
	long md1=1, md2=1;
	for (i=0; i<n; ++i) {
		hash1 = (hash1*t+A[i])%pr1;
		hash2 = (hash2*t+A[i])%pr2;
		if (i) { md1 = (md1*t)%pr1; md2 = (md2*t)%pr2; }
	}

	// cautam pozitii-candidat
	for (i=0; i<m; ++i) {
		if ( i<n ) {
			test1 = (test1*t + B[i])%pr1;
			test2 = (test2*t + B[i])%pr2;
		} else {
	        test1 = ((pr1+test1-(B[i-n]*md1)%pr1)*t+B[i])%pr1;
			test2 = ((pr2+test2-(B[i-n]*md2)%pr2)*t+B[i])%pr2;
			if ( test1==hash1 && test2==hash2 )
				if ( go_real(i-n+1) ) {
					nr ++;
					if ( Save[0]<1000 )
						Save[++Save[0]] = i-n+1;
				}
		}
	}

	freopen("strmatch.out", "w", stdout);
	printf("%ld\n", nr);
	for (i=1; i<=Save[0]; ++i)
		printf("%ld ", Save[i]);
	return 0;
}