Cod sursa(job #169905)

Utilizator swift90Ionut Bogdanescu swift90 Data 2 aprilie 2008 10:50:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include<stdio.h>
#include<string.h>
#define lg 2000010
char s1[lg],s2[lg],sir1[lg],sir2[lg];
int n,m,pr[lg],rez[1001],rezultat;
void prefix(){
	int k,i;
	k=0;
	for(i=2;i<=n;++i){
		while(k>0 && sir1[k+1]!=sir1[i])
			k=pr[k];
		if(sir1[k+1]==sir1[i])
			++k;
		pr[i]=k;
	}
}
int main(){
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	int i,k;
	scanf("%s%s",s1,s2);
	n=strlen(s1);
	m=strlen(s2);
	for(i=0;i<n;++i)
		sir1[i+1]=s1[i];
	for(i=0;i<m;++i)
		sir2[i+1]=s2[i];
	
	prefix();
	k=0;
	for(i=1;i<=m;++i){
		while(k>0 && sir1[k+1]!=sir2[i])
			k=pr[k];
		if(sir1[k+1]==sir2[i])
			++k;
		if(k==n){
			++rezultat;
			if(rezultat<=1000)
				rez[rezultat]=i-n;
		}
	}
	
	printf("%d\n",rezultat);
	if(rezultat>1000){
		for(i=1;i<1000;++i)
			printf("%d ",rez[i]);
		printf("%d\n",rez[i]);
	}
	else{
		if(rezultat){
			for(i=1;i<rezultat;++i)
				printf("%d ",rez[i]);
			printf("%d\n",rez[rezultat]);
		}
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}