Cod sursa(job #392335)

Utilizator BaduBadu Badu Badu Data 7 februarie 2010 13:31:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<cstdio>
#include<string.h>
#define max 2000005

int n,m,pre[max],sol[1001];
char P[max],T[max];

void Prefix(){
	
	int i,x;
	
	for( i=1, x=-1; i<=m;i++){

			while( x > 0 && P[ x+1 ] != P[ i ]) x = pre[x];
			if( P[ x+1 ] == P [i] ) x++;
			
			pre[i] = x;
	}
}

int main(){
	
	FILE *f=fopen("strmatch.in","r");
	FILE *g=fopen("strmatch.out","w"); 
	
	fscanf(f,"%s\n%s",P,T);
	
	m = strlen(P);
	n = strlen(T);
	
	Prefix();
	int i,x,k=0;

	x=-1;
	
	for( i=0; i<=n;i++){
		
		while( x>0 && P [ x+1 ] != T [i] ) x = pre[x];
		if( P[ x+1 ] == T [i] ) x++;
		if( x == m-1 ){
			k++;
			if( k<1001 ) sol[k] = i - m + 1;
			x = pre[x];
		}
	}
	fprintf(g,"%d\n",k);
	
	k = k>1000?1000:k;
	for(i=1;i<=k;i++) fprintf(g,"%d ",sol[i]);
	
	
	return 0;
}