Cod sursa(job #349449)

Utilizator vlad.maneaVlad Manea vlad.manea Data 19 septembrie 2009 17:00:46
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>

char P[2000002], T[2000002];
int U, V, Q, F, M, N, X, Y;
int R[1002];

int main()
{
	int i, k, l;

	Q = 666013;
	F = 727777;


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

	gets(P);
	gets(T);

	for (M = 0; P[M]; ++M);
	for (N = 0; T[N]; ++N);

	for (i = 0; i < M; ++i)
	{
		U = (U + P[i]) % Q;
		X = (X + P[i]) % F;
	}

	for (i = 0; i < M; ++i)
	{
		V = (V + T[i]) % Q;
		Y = (Y + T[i]) % F;
	}

	for (i = M-1; i < N; ++i)
	{
		if (V == U && X == Y)
		{
			/*for (k = 0, l = i-M+1; k < M; ++k, ++l)
				if (P[k] != T[l])
					break;

			if (k == M)
			{*/
				++R[0];
				if (R[0] <= 1000)
					R[R[0]] = i-M+1;
				/*
			}*/
		}

		V -= T[i-M+1];
		V += T[i+1];
		while (V < 0)
			V += Q;

		Y -= T[i-M+1];
		Y += T[i+1];
		while (Y < 0)
			Y += F;
	}

	printf("%d\n", R[0]);
	if (R[0] > 1000) R[0] = 1000;
	for (i = 1; i <= R[0]; ++i)
		printf("%d ", R[i]);
	printf("\n");

	return 0;
}