Cod sursa(job #270505)

Utilizator BaduBadu Badu Badu Data 4 martie 2009 08:47:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<stdio.h>
#include<string.h>

char P[1000000],D[1000000];
int  U[1000000],s[1000],n,m,nr;

void Prefix(){

	int i,k=-1;

	U[0]=0;

	for(i=1;i<m;i++){

		while(k>0 && P[k+1]!=P[i]) k = U[k];

		if(P[k+1] == P[i]) k++;

		U[i] = k;

	}

}

void Matches(){

	int i,k=-1;

	for(i=0;i<n;i++){

		while(k>0 && P[k+1]!=D[i]) k = U[k];

		if(P[k+1] == D[i]) k++;

		if(k == m-1 ) {

			nr++;

			if(nr<=1000) s[nr-1]=i-m+1;

			k = U[k];

		}
	}

}

int main(){

	FILE *f = fopen("strmatch.in","r");
	FILE *g = fopen("strmatch.out","w");

	fscanf(f,"%s\n",P);
	fscanf(f,"%s",  D);

	m = strlen(P);
	n = strlen(D);

	Prefix();

	Matches();

	fprintf(g,"%d\n",nr);

	if(nr>1000) nr=1000;

	for(int i=0;i<nr;i++) fprintf(g,"%d ",s[i]);

	return 0;

}