Cod sursa(job #182222)

Utilizator Spike7d8Cristian Varvara Spike7d8 Data 20 aprilie 2008 15:33:31
Problema Potrivirea sirurilor Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.31 kb
#ifdef WIN32
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>
#include <string.h>


#define MUL1 101
#define MUL2 107
#define MOD1 1000001
#define MOD2 1000007

char a[2000896], b[2000896], sol[1024];


int main()
{
	freopen("strmatch.in", "rt", stdin);
	freopen("strmatch.out", "wt", stdout);

	scanf("%s %s", a, b);
	int la = strlen(a), lb = strlen(b);

	if (la > lb)
	{
		printf("0\n");
		return 0;
	}

	int a1 = 0, a2 = 0;
	int b1 = 0, b2 = 0;
	int p1 = 1, p2 = 1;

	for (int i = 0; i < la; i++)
	{
		a1 = (a1 * MUL1 + a[i]) % MOD1;
		a2 = (a2 * MUL2 + a[i]) % MOD2;

		b1 = (b1 * MUL1 + b[i]) % MOD1;
		b2 = (b2 * MUL2 + b[i]) % MOD2;

		if (i)
		{
			p1 = (p1 * MUL1) % MOD1;
			p2 = (p2 * MUL2) % MOD2;
		}
	}


	int nsol = 0;
	if (a1 == b1 && a2 == b2)
	{
		nsol++;
		sol[0] = 0;
	}

	for (int i = la; i < lb; i++)
	{
		b1 = ((b1 - (b[i - la] * p1) % MOD1 + MOD1) * MUL1 + b[i]) % MOD1;
		b2 = ((b2 - (b[i - la] * p2) % MOD2 + MOD2) * MUL2 + b[i]) % MOD2;

		if (a1 == b1 && a2 == b2)
		{
			nsol++;
			if (nsol <= 1000)
				sol[nsol] = i - la + 1;
		}
	}


	if (nsol == 0)
		printf("0\n");
	else
	{
		printf("%d\n", nsol);
		for (int i = 1; i <= ((nsol > 1000)? 1000 : nsol); i++)
			printf("%d ", sol[i]);
		printf("\n");
	}

	return 0;
}