Cod sursa(job #143808)

Utilizator vlad.maneaVlad Manea vlad.manea Data 26 februarie 2008 21:19:56
Problema Potrivirea sirurilor Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <stdio.h>
#include <string.h>

#define prim 97
#define nmax 2048000
#define mmax 2048000
#define find 1024

char T[nmax], P[mmax];

int V[find];

int N, M, i, pattern, modulo, j, ok, k;



int main(void)
{
	freopen("strmatch.in", "r", stdin);

	freopen("strmatch.out", "w", stdout);

	scanf("%s\n", P);

	scanf("%s", T);

	N = strlen(T);

	M = strlen(P);

	for (i = 0; i < M; ++i)
	{
		pattern = (pattern + P[i] - 'a') % prim;
		modulo = (modulo + T[i] - 'a') % prim;
	}

	for (i = 0; i <= N - M; ++i)
	{
		if (modulo == pattern)
		{
			for (j = i, ok = 1; j < i + M && ok; ++j)
				if (T[j] != P[j-i]) ok = 0;
			if (ok && k < 1000)
					V[++k] = i;
		}

		modulo = (modulo + T[i + M] - T[i] % prim) % prim;
	}

	printf("%d\n", k);

	for (i = 1; i < k; ++i) printf("%d ", V[i]); printf("%d\n", V[i]);

	return 0;
}