Cod sursa(job #169923)

Utilizator MirageRobert Sandu Mirage Data 2 aprilie 2008 11:04:30
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<stdio.h>
#include<string.h>
int main () {
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	char a[2000010],b[2000010];
	int m,n,i,k=0,pi[2000010],v[1000],q=0;
	fgets(a+1,2000010,stdin);
	fgets(b+1,2000010,stdin);
	n=strlen(a+1);
	m=strlen(b+1);
	--n;--m;
	pi[0]=0;
	pi[1]=0;
	for(i=2;i<=n;++i){
		while((k>0)&&(a[k+1]!=a[i]))
			k=pi[k];
		if(a[k+1]==a[i])
			++k;
		pi[i]=k;
	}
	k=0;
	for(i=1;i<=m;++i){
		while((k>0)&&(a[k+1]!=b[i]))
			k=pi[k];
		if(a[k+1]==b[i])
			++k;
		if(k==n){
			if(q<1000)
				v[q]=i-n;
			++q;
		}
	}
	printf("%d\n",q);
	if(q){
		for(i=0;i<q&&i<999;++i)
			printf("%d ",v[i]);
		printf("\n");
	}
	return 0;
}