Cod sursa(job #425568)

Utilizator NemultumituMatei Ionita Nemultumitu Data 25 martie 2010 21:14:12
Problema Potrivirea sirurilor Scor 22
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <cstdio>
#include <cstring>
char a[2000050],b[2000050];
int pia[2000050],pib[2000050];


int main()
{
	freopen ("strmatch.in","r",stdin);
	freopen ("strmatch.out","w",stdout);
	gets(a);
	gets(b);
	int i;
	for (i=1;a[i];++i)
	{
		if (a[i]==a[0])
			pia[i]=1;
		int y=i-1;
		while (y+1)
		{
			if (a[pia[y]]==a[i]&&pia[y]+1>pia[i])
				pia[i]=pia[y]+1;
			y=pia[y]-1;
		}
	}
	if (b[0]==a[0])
		pib[0]=1;
	bool k;
	for (i=1;b[i];++i)
	{
		k=0;
		if (b[i]==a[0])
			pib[i]=1;
		int y=pib[i-1]-1;
		if (a[pib[i-1]]==b[i])
		{
			pib[i]=pib[i-1]+1;
			continue;
		}
		while (y&&!k)
		{
			if (a[y]==b[i])
			{
				pib[i]=y+1;
				k=1;
			}
			y=pia[y];
		}
	}
	int n=strlen(a),cnt=0;
	for (i=0;b[i];++i)
		if (pib[i]==n)
			++cnt;
	printf("%d\n",cnt);
	for (i=0;b[i];++i)
		if (pib[i]==n)
			printf("%d ",i-n+1);
	printf("\n");
	return 0;
}