Cod sursa(job #505673)

Utilizator chiar_nimeninimeni chiar_nimeni Data 3 decembrie 2010 16:09:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 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;

inline 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){
			q = pi[q];
			++nr;
			if (nr<=1000)
				d[nr]=i-m;
	}
}
printf ("%d\n",nr);
if (nr>1000)
{
	for (i=1; i<=1000; i++)
		printf ("%d ",d[i]);
	printf ("\n");
}
else
{
for (i=1; i<=nr; i++)
	printf ("%d ",d[i]);
printf ("\n");
}
return 0;
}