Cod sursa(job #505718)

Utilizator George25Raduta George Cristian George25 Data 3 decembrie 2010 18:26:23
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
# include <stdio.h> 
# include <string.h> 
char a[2000010],b[2000100]; 
int qq[2000010],c[2000010];
int i,j,n,m,t,nr,k;
inline void creare (){ 
	k=0;
	qq[1]=0;
	for (i=2; i<=m; i++){
		while (k>0 && b[k+1]!=b[i])
			k=qq[k];
		if (b[i]==b[k+1])
			k++;
		qq[i]=k;
	}
} 
 
 
int main (){ 
	freopen ("strmatch.in ","r",stdin); 	
	freopen ("strmatch.out","w",stdout); 
	gets(b+1); 
	gets(a+1); 
	n=strlen(a+1); 
	m=strlen(b+1); 
	creare(); 
	t=0; 
	for (i=1; i<=n; i++){
		while (t>0 && b[t+1]!=a[i])
			t=qq[t];
		if (b[t+1]==a[i]) t++;
		if (t==m){
			t=qq[t];
			nr++;
			if (nr<=1000) c[nr]=i-m; 
		}
	}		
	printf ("%d\n",nr); 
	if (nr>1000){
		for (i=1; i<=1000; i++)
			printf ("%d ",c[i]);
		printf ("\n");
	}
	else{ 
		for (i=1; i<=nr; i++)    
			printf ("%d ",c[i]); 
		printf ("\n"); 
	}
	return (0); 
}