Cod sursa(job #440555)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 12 aprilie 2010 08:42:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <cstdio>
#include <cstring>
#include <string>

#define nmax 2000005
#define unmax 10005

using namespace std;

char a [nmax], b [nmax];
int urm [nmax], sol [unmax], cnt, n, m;
void prefix ()
{
	int i, k;
	k = 0;
	for (i = 2; i <= n; i++)
	{
		while (k > 0 && a [k + 1] != a [i])
			k = urm [k];
		if (a [k + 1] == a [i])
			++k;
		urm [i] = k;
	}
}
void kmp ()
{
	int i, k;
	k = 0;
	for (i = 1; i <= m;  i++)
	{
		while (k > 0 && a [k + 1] != b [i])
			k = urm [k];
		if (a [k + 1] == b [i])
			++k;
		if (k == n)
	       	{
			if (cnt < 1000)	sol [++cnt] = i - n;
			else ++cnt;
		}
	}
	printf ("%d\n", cnt);
	for (i = 1; i <= min (cnt, 1000); i++)
		printf ("%d ", sol [i]);
}
int main ()
{
	freopen ("strmatch.in", "r", stdin);
	freopen ("strmatch.out", "w", stdout);
	scanf ("%s\n%s\n", a + 1, b + 1);
	n = strlen (a + 1);
	m = strlen (b + 1);
	prefix ();
	kmp ();
	return 0;
}