Cod sursa(job #147338)

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

const long prime = 6997;
const long MAX = 2000010;	// TODO : de pus la loc

char A[MAX], B[MAX];
long n,m,hash, test,nr;
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) {
	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)
		hash = (hash+A[i])%prime;

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