Cod sursa(job #685683)

Utilizator KoniacDocea Andrei Koniac Data 21 februarie 2012 08:59:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<stdio.h>
#include<string.h>
#define lim 2000010

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

char N[lim],M[lim];
int n,m,k,q,nr,poz[1111],p[lim];

void prefix(){
	k=0;
	p[1]=0;
	for(int i=2;i<=n;i++){
		while(k>0 && (N[k+1]!=N[i]) )
			k=p[k];
		if(N[k+1]==N[i])
			k++;
		p[i]=k;
	}
}

void match(){
	q=0;
	for(int i=1;i<=m;i++){
		while(q>0 && (N[q+1]!=M[i]) )
			q=p[q];
		if(N[q+1]==M[i])
			q++;
		if(q==n){
			nr++;
			if(nr<=1000)
				poz[nr]=i-n;;
		}
	}
	
}


int main(){
	fscanf(f,"%s",N+1);
	fscanf(f,"/n");
	fscanf(f,"%s",M+1);
	n=strlen(N+1);
	m=strlen(M+1);
	prefix();
	match();
	fprintf(g,"%d\n",nr);
	for(int i=1;i<=nr&&i<=1000;i++)
		fprintf(g,"%d ",poz[i]);
	fprintf(g,"\n");
	
	fclose(f);
	fclose(g);
	return 0;
}