Cod sursa(job #153041)

Utilizator peanutzAndrei Homorodean peanutz Data 10 martie 2008 01:58:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <stdio.h>
#include <string.h>

#define NMAX 2000050

#define P 73
#define MOD1 100023
#define MOD2 100007

char a[NMAX], b[NMAX];
long n, m;
long ap[1010], h;
long na, nb;
long ha1, ha2, hb1, hb2;
long nr;
long p1, p2;

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

	scanf("%s", a+1);
	scanf("%s", b+1);
	na = strlen(a+1);
	nb = strlen(b+1);

	if(na > nb)
	{
		printf("0");
		return 0;
	}

        p1 = p2 = 1;
	for(i = 1; i <= na; ++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 != 1)
			p1 = (p1*P) % MOD1,
			p2 = (p2*P) % MOD2;
	}

	if(ha1 == hb1 && ha2 == hb2)
		ap[++h] = 0;


	for(i = na+1; i <= nb; ++i)
	{
		hb1 = ( (hb1 - (p1*b[i-na]) % MOD1 + MOD1) * P + b[i] ) % MOD1;
		hb2 = ( (hb2 - (p2*b[i-na]) % MOD2 + MOD2) * P + b[i] ) % MOD2;

		if(ha1 == hb1 && ha2 == hb2)
		{
			if(h < 1000)
				ap[++h] = i-na;
			else
				++h;
		}
	}

	printf("%ld\n", h);
	for(i = 1; i <= 1000 && i <= h; ++i)
		printf("%ld ", ap[i]);

	return 0;
}