Cod sursa(job #147385)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 2 martie 2008 20:59:32
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <cstdio>
#include <cstring>

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

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

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
	for (i=0; i<n; ++i) {
		hash1 = (hash1+A[i])%pr1;
		hash2 = (hash2+A[i])%pr2;
	}

	// cautam pozitii-candidat
	for (i=0; i<m; ++i) {
		test1 = (test1 + B[i])%pr1;
		test2 = (test2 + B[i])%pr2;
        if ( i>=n ) {
	        test1 = (pr1+test1-B[i-n])%pr1;
			test2 = (pr2+test2-B[i-n])%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;
}