Cod sursa(job #681646)

Utilizator aloneForever Alone alone Data 17 februarie 2012 16:41:54
Problema Potrivirea sirurilor Scor 92
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <cstdio>
#include <cstring>

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

#define Ai (A[i] - 'A')
#define Bi (B[i] - 'A')

char A[NMAX], B[NMAX];
int V[1024], N, P1, P2;

void rabin_karp (), input (), output ();

int main () {
	
	input ();
	
	rabin_karp ();
	
	output ();
	
	return 0;
}

void rabin_karp () {
	
	A[0] = ' ', B[0] = ' ';
	int NA = strlen (A) - 1; int NB = strlen (B) - 1;
	
	int i, HA1 = 0, HA2 = 0, H1 = 0, H2 = 0; P1 = P2 = 1;
	for (i = 1; i <= NA; i++) {
		HA1 = (HA1 * P + Ai) % MOD1;
		HA2 = (HA2 * P + Ai) % MOD2;
		
		H1 = (H1 * P + Bi) % MOD1;
		H2 = (H2 * P + Bi) % MOD2;
		
		if (i < NA)
			P1 = (P1 * P) % MOD1, P2 = (P2 * P) % MOD2;
	}
	
	if (H1 == HA1 && H2 == HA2) V[++N] = 0;
	
	for (i = NA + 1; i <= NB; i++) {
		H1 = ((H1 - ((B[i - NA] - 'A') * P1) % MOD1 + MOD1) * P + Bi) % MOD1;
		H2 = ((H2 - ((B[i - NA] - 'A') * P2) % MOD2 + MOD2) * P + Bi) % MOD2;
		
		if (H1 == HA1 && H2 == HA2) {
			N++;
			if (N <= 1000) V[N] = i - NA;
		}
	}
}

void input () {
	
	freopen ("strmatch.in", "r", stdin);
	
	scanf ("%s %s", A + 1, B + 1);
}

void output () {
	
	freopen ("strmatch.out", "w", stdout);
	
	printf ("%d\n", N);
	for (int i = 1; i <= N && i <= 1000; i++)
		printf ("%d ", V[i]);
}