Cod sursa(job #420186)

Utilizator laserbeamBalan Catalin laserbeam Data 18 martie 2010 17:16:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
// Catalin Balan
// Thu Mar 18 16:40:00 EET 2010
// KMP

#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

#define NMAX 2000015

#define FIN "strmatch.in"
#define FOUT "strmatch.out"

char A[NMAX], B[NMAX];
int pref[NMAX];
int rez[1024];
int N,M;

void makePrefix()
{
	pref[1] = 0;
	for (int i = 2, p = 0; i <= N; ++i)
	{
		while (p && A[i] != A[p+1]) p = pref[p];
		if (A[i] == A[p+1]) ++p;
		pref[i] = p;
	}

}

int main(int argv, char ** argc)
{
	freopen(FIN, "r", stdin);
	freopen(FOUT, "w", stdout);

	gets(A);
	gets(B);

	N = strlen(A);
	M = strlen(B);
	for (int i = N; i; --i) A[i] = A[i-1];
	for (int i = M; i; --i) B[i] = B[i-1];
	A[0] = B[0] = ' ';
	A[N+1] = 0;
	makePrefix();

	int cate = 0;
	for (int i = 1, p = 0; i <= M; ++i)
	{
		while (p && B[i] != A[p+1]) p = pref[p];
		if ( B[i] == A[p+1]) ++p;

		if (p == N)
		{
			p = pref[p];
			++cate;
			if (cate <= 1000)
			{
				rez[cate] = i-N;
			}
		}

	}
	
	printf("%d\n", cate);
	if (cate > 1000) cate = 1000;
	for (int i = 1; i <= cate; ++i)
	{
		printf("%d ", rez[i]);
	}

	return EXIT_SUCCESS;
}