Cod sursa(job #169897)

Utilizator slayer4uVictor Popescu slayer4u Data 2 aprilie 2008 10:45:18
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <stdio.h>
#include <string.h>

char S[2000100], W[2000100];
long T[2000100];
long i, j, m, ns, nw, nx, x[2000100];

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

	scanf("%s\n%s", &W, &S);

	ns = strlen(S);
	nw = strlen(W);

	i = 2;
	j = 0;
	T[1] = 0;
	T[0] = -1;
	while (i < nw)
	{
		if (W[i - 1] == W[j])
			T[i] = j + 1, ++i, ++j;
		else
		if (j > 0)
			j = T[j];
		else
			T[i] = 0, ++i;
	}

	m = i = 0;
	while (m + i < ns)
	{
		if (W[i] == S[m + i])
		{
			++i;
			if (i == nw)
			{
				x[++nx] = m;
				//printf("%ld ", m);
				i = T[i];
				++m;
			}
		}
		else
		{
			m = m + i - T[i];
			if (i > 0)
				i = T[i];
		}
	}

	printf("%ld\n", nx);

	nx = nx < 1000 ? nx : 1000;
	for (i = 1; i <= nx; ++i)
		printf("%ld ", x[i]);
	printf("\n");
	return 0;
}