Cod sursa(job #166128)

Utilizator vlad.maneaVlad Manea vlad.manea Data 27 martie 2008 14:35:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <stdio.h>
#include <string.h>
#define nmax 2000008

char T[nmax], P[nmax];

int E[1005], pi[nmax];

int N, M, Q;

void read()
{
	freopen("strmatch.in", "r", stdin);
	scanf("%s\n", &P);
	scanf("%s", &T);
}

void prefix()
{
	int i, k;

	for (i = 2, k = 0; i <= M; ++i)
	{
		k = pi[i-1];

		while (k && P[k+1] != P[i])
			k = pi[k];

		if (P[k+1] == P[i])
			++k;

		pi[i] = k;
	}
}

void kmp()
{
	int i, k;

	for (i = 1, k = 0; i <= N; ++i)
	{
		while (k && T[i] != P[k+1])
			k = pi[k];

		if (P[k+1] == T[i])
			++k;

		if (k == M)
		{
			k = pi[k];

			++Q;
			if (Q <= 1000)
				E[Q] = i-M;
		}
	}
}

void solve()
{
	int i;

	N = strlen(T);
	M = strlen(P);
	for (i = N; i; i--)
		T[i] = T[i-1];
	for (i = M; i; i--)
		P[i] = P[i-1];

	T[0] = P[0] = ' ';

	prefix();

	kmp();
}

void write()
{
	int i;

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

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

	Q = Q < N? Q: N;

	for (i = 1; i <= Q; ++i)
		printf("%d ", E[i]);
}

int main()
{
	read();

	solve();

	write();

	return 0;
}