Cod sursa(job #493487)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 18 octombrie 2010 15:52:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <stdio.h>
#include <string.h>

#define DIM 2000002
#define LIMIT 1000
#define BZ 73
#define MOD1 100002
#define MOD2 100067

int P1, P2;

char A[DIM], B[DIM];
int NA, NB, hashA1, hashA2, hashB1, hashB2;
int match[LIMIT], NR;

void cit () 
{
	scanf ("%s%s", A, B);
	NA = strlen (A);
	NB = strlen (B);
}

void hash ()
{
	P1 = P2 = 1; 
	
	for (int i = 0; i < NA; ++i)
	{
		hashA1 = (hashA1 * BZ + A[i]) % MOD1, 
		hashA2 = (hashA2 * BZ + A[i]) % MOD2;
		
		hashB1 = (hashB1 * BZ + B[i]) % MOD1,
		hashB2 = (hashB2 * BZ + B[i]) % MOD2;
		
		if (i != 0)
		{
			P1 = (P1 * BZ) % MOD1;
			P2 = (P2 * BZ) % MOD2;
		}
	}
	
	if (hashA1 == hashB1 && hashA2 == hashB2)
		match[NR++] = 0;
	
	for (int i = NA; i < NB; ++i) 
	{
		hashB1 = ((hashB1 - (B[i - NA] * P1) % MOD1 + MOD1) * BZ + B[i]) % MOD1,
		hashB2 = ((hashB2 - (B[i - NA] * P2) % MOD2 + MOD2) * BZ + B[i]) % MOD2;
		
		if (hashA1 == hashB1 && hashA2 == hashB2)
		{		
			if (NR < LIMIT)
				match[NR] = i - NA + 1;
			++NR;
		}
	}	
}

void afs ()
{
	printf ("%d\n", NR);
	
	if (NR > LIMIT) NR = LIMIT;
	
	for (int i = 0; i < NR; ++i)
		printf ("%d ", match[i]);
}

int main ()
{
	freopen ("strmatch.in", "r", stdin);
	freopen ("strmatch.out", "w", stdout);
	
	cit ();
	hash ();
	afs ();
	
	return 0;
}