Cod sursa(job #530625)

Utilizator Gaby_mMititelu Gabriel Gaby_m Data 8 februarie 2011 01:51:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include<cstdio>
#include<cstring>

using namespace std;

#define P 73
#define Prim1 100007
#define Prim2 100021

#define MAXS 200001

char A[MAXS], B[MAXS];
int Na, Nb;

int hash1, hash2, P1, P2;

int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	scanf("%s %s", A, B);
	Na = strlen(A);
	Nb = strlen(B);

	if (Na > Nb) {
		printf("0\n");
		return 0;
	}

	P1 = P2 = 1;
	hash1 = hash2 = 0;

	for (int i = 0; i < Na; i++) {
		hash1 = (hash1 * P + A[i]) % Prim1;
		hash2 = (hash2 * P + A[i]) % Prim2;

		if (i) {
			P1 = (P1 * P) % Prim1;
			P2 = (P2 * P) % Prim2;
		}
	}

	int hits[MAXS];
	int N, auxH1, auxH2;
	N = 0; 
	auxH1 = auxH2 = 0;
	for (int i = 0; i < Na; i++) {
		auxH1 = (auxH1 * P + B[i]) % Prim1;
		auxH2 = (auxH2 * P + B[i]) % Prim2;
	}

	if (hash1 == auxH1 && hash2 == auxH2) hits[N++] = 1;

	for (int i = Na; i < Nb; i++) {
		auxH1 = ((auxH1 - (B[i-Na] * P1) % Prim1 + Prim1) * P + B[i]) % Prim1;
		auxH2 = ((auxH2 - (B[i-Na] * P2) % Prim2 + Prim2) * P + B[i]) % Prim2;

		if (hash1 == auxH1 && hash2 == auxH2) {
			hits[i - Na + 1] = 1;
			N++;
		}
	}

	printf("%d\n", N);
	N = 0;
	for (int i = 0; i < Nb && N < 1000; i++){
		if (hits[i] == 1) {
			printf("%d ", i);
			N++;
		}
	}
	printf("\n");

	return 0;

}