Cod sursa(job #458673)

Utilizator Addy.Adrian Draghici Addy. Data 25 mai 2010 19:06:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <cstdio>
#include <cstring>

#define NMAX 200050
#define	P 97
#define MOD1 100021
#define MOD2 100017

char A[NMAX], B[NMAX];
int sol[1024], NA, NB, P1, P2, i, HASH_A1, HASH_A2, HASH_X1, HASH_X2, N;

int main() {
	
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	
	scanf("%s %s", A + 1, B + 1);
	A[0] = ' ', B[0] = ' ', NA = strlen(A) - 1, NB = strlen(B) - 1;
	
	P1 = P2 = 1;
	for (i = 1; i <= NA; i++) {
		HASH_A1 = (HASH_A1 * P + A[i]) % MOD1;
		HASH_A2 = (HASH_A2 * P + A[i]) % MOD2;
		if (i < NA)
			P1 = (P1 * P) % MOD1, P2 = (P2 * P) % MOD2;
	}
	
	for (i = 1; i <= NA; i++) {
		HASH_X1 = (HASH_X1 * P + B[i]) % MOD1;
		HASH_X2 = (HASH_X2 * P + B[i]) % MOD2;
	}
	
	if (HASH_A1 == HASH_X1 && HASH_A2 == HASH_X2) sol[++N] = 1;
	
	for (i = NA + 1; i <= NB; i++) {
		HASH_X1 = ((HASH_X1 - (B[i - NA] * P1) % MOD1 + MOD1) * P + B[i]) % MOD1;
		HASH_X2 = ((HASH_X2 - (B[i - NA] * P2) % MOD2 + MOD2) * P + B[i]) % MOD2;
		
		if (HASH_A1 == HASH_X1 && HASH_A2 == HASH_X2) {
			N++;
			if (N <= 1000)
				sol[N] = i - NA + 1;
		}
	}
	
	printf("%d\n", N);
	for (i = 1; i <= N && i <= 1000; i++)
		printf("%d ", sol[i] - 1);
	
	return 0;
}