Cod sursa(job #898017)

Utilizator Alex_Merceraaaaaaa Alex_Mercer Data 27 februarie 2013 23:46:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int pi[2100000],n,m,i,nr,poz[1100],q;
char a[2100000],b[2100000];

void piu ()
{
	int i,q;
	q = 0; pi[0] = 0;
	for (i=2; i<=n; i++)
	{
		while (q && a[i] != a[q+1])
			q = pi[q];
		if (a[i] == a[q+1]) q++;
		pi[i] = q;
	}
	return;
}

int main()
{
	freopen ("strmatch.in","r",stdin);
	freopen ("strmatch.out","w",stdout);

	gets(a+1);
	gets(b+1);

	n = strlen(a+1);
	m = strlen(b+1);

	piu();

	nr = 0;

	for (i=1; i<=m; i++)
	{
		while (q && a[q+1] != b[i]) q = pi[q];
		if (a[q+1] == b[i]) q++;
		if (q == n)
		{
			nr++;
			if (nr<=1000)
			{
				poz[nr] = i - n ;
			}
		}
	}

	printf ("%d\n",nr);
	for (i=1; i<=min(nr,1000); i++) printf ("%d ",poz[i]);
	printf ("\n");
	return 0;
}