Cod sursa(job #505648)

Utilizator chiar_nimeninimeni chiar_nimeni Data 3 decembrie 2010 13:56:48
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
# include <stdio.h>
# include <string.h>

# define maxl 2001000

char a[2001000],b[2001000];
int pi[2001000],d[2001000],nr,n,m,q,i,k;

void creare ()
{
	int i;
	k=0;
	pi[1]=0;
	for (i=2; i<=m; i++)
	{
		while (k>0 && b[k+1]!=b[i])
			k=pi[k];
		if (b[i]==b[k+1])
			k++;
		pi[i]=k;
	}
}

int main ()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
fgets (b+1,maxl,stdin);
fgets (a+1,maxl,stdin);
n=strlen(a+1)-1;
m=strlen(b+1)-1;
creare();
q=0;
for (i=1; i<=n; i++)
{
	while (q>0 && b[q+1]!=a[i])
		q=pi[q];
	if (b[q+1]==a[i]) q++;
		if (q==m)
			d[++nr]=i-m;
}
printf ("%d\n",nr);
for (i=1; i<=nr; i++)
	printf ("%d ",d[i]);
printf ("\n");
return 0;
}