Cod sursa(job #557626)

Utilizator cnt_tstcont teste cnt_tst Data 16 martie 2011 18:56:16
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <cstdio>
#include <cstring>

#define NMAX 2000050
#define P 97
#define MOD1 666013
#define MOD2 13931

bool V[NMAX];
char A[NMAX], B[NMAX];
int HA1, HB1, P1, HA2, HB2, P2, nr, n, m, i;

int main () {
	
	freopen ("strmatch.in", "r", stdin);
	freopen ("strmatch.out", "w", stdout);
	
	scanf ("%s\n%s", A, B);
	n = strlen (A), m = strlen (B);
	
	P1 = P2 = 1;
	for (i = 0; i < n; i++) {
		HA1 = (HA1 * P + A[i]) % MOD1;
		HA2 = (HA2 * P + A[i]) % MOD2;
		
		HB1 = (HB1 * P + B[i]) % MOD1;
		HB2 = (HB2 * P + B[i]) % MOD2;
		
		if (i > 0)
			P1 = (P1 * P) % MOD1, P2 = (P2 * P) % MOD2;
	}
	
	if (HA1 == HB1 && HA2 == HB2)
		nr++, V[0] = 1;
	
	for (i = n; i < m; i++) {
		HB1 = ((HB1 - (P1 * B[i - n]) % MOD1 + MOD1) * P + B[i]) % MOD1;
		HB2 = ((HB2 - (P2 * B[i - n]) % MOD2 + MOD2) * P + B[i]) % MOD2;
		
		if (HA1 == HB1 && HA2 == HB2)
			nr++, V[i - n + 1] = 1;
	}
	
	printf ("%d\n", nr);
	
	nr = 0;
	for (i = 0; i < m && nr < 1000; i++)
		if (V[i]) {
			nr++;
			printf ("%d ", i);
		}
	
	return 0;
}