Cod sursa(job #432238)

Utilizator NemultumituMatei Ionita Nemultumitu Data 1 aprilie 2010 23:28:37
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <cstdio>
#include <cstring>
char a[2000010],b[2000010];
int n,m,cnt,pia[2000010],pib[2000010];

void citire()
{
	freopen ("strmatch.in","r",stdin);
	freopen ("strmatch.out","w",stdout);
	gets(a);
	gets(b);
	n=strlen(a);
	m=strlen(b);
	for (int i=n;i;--i)
		a[i]=a[i-1];
	a[0]='$';
	for (int i=m;i;--i)
		b[i]=b[i-1];
	b[0]='$';
}

int main()
{
	citire();
	int i;
	for (i=2;a[i];++i)
	{
		int y=pia[i-1];
		while (a[y+1]!=a[i]&&y)
			y=pia[y];
		if (a[y+1]==a[i])
			pia[i]=y+1;
	}
	for (int i=1;b[i];++i)
	{
		int y=pib[i-1];
		while (a[y+1]!=b[i]&&y)
			y=pia[y];
		if (a[y+1]==b[i])
			pib[i]=y+1;
		if (pib[i]==n)
			++cnt;
	}
	printf("%d\n",cnt);
	cnt=0;
	for (int i=1;i<=m;++i)
		if (pib[i]==n)
			if (cnt==1000)
				break;
			else
			{
				printf("%d ",i-n);
				++cnt;
			}
	return 0;
}