Cod sursa(job #444821)

Utilizator nandoLicker Nandor nando Data 21 aprilie 2010 19:45:34
Problema Potrivirea sirurilor Scor 28
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>

FILE* fin=fopen("strmatch.in","r");
FILE* fout=fopen("strmatch.out","w");

#define MAX 2000005
#define MAXM 1005
#define isChar(a) (('a'<=(a)&&(a)<='z')||('A'<=(a)&&(a)<='Z'))
#define min(a,b) (((a)<(b))?(a):(b))

char A[MAX],B[MAX];
int pi[MAX],n=1,m=1,match[MAXM],nrm=0;

void build_prefix(){
	pi[1]=0;
	for(int q=2,k=0;q<=m;q++){
		while(k && A[k+1]!=A[q])
			k = pi[k];
		if(A[k+1]==A[q])
			k++;
		pi[q]=k;	
	}
}

void kmp(){
	for(int i=1,q=0;i<=n;i++){
		while(q && A[q+1]!=B[i])
			q=pi[q];
		if(A[q+1]==B[i])
			q++;
		if(q==m){
			nrm++;
			if(nrm<=MAXM)
				match[nrm]=i-m;
			q=pi[q];
		}
	}	
}

int main(){
	A[0]=B[0]=' ';
	fgets(A+1,MAX,fin);
	fgets(B+1,MAX,fin);
	
	while(isChar(A[m]))m++;	
	while(isChar(B[n]))n++;
	n--,m--;
	
	build_prefix();
	kmp();
	
	fprintf(fout,"%d\n",nrm);
	for(int i=1;i<=min(nrm,MAXM);i++){
		fprintf(fout,"%d ",match[i]);	
	}
	
	
	fclose(fin);
	fclose(fout);
	return 0;
}