Cod sursa(job #397233)

Utilizator BaduBadu Badu Badu Data 16 februarie 2010 18:11:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<cstdio>
#include<cstring>
#define max 2000005

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

void prefix(){
	
	int i,k;
	
	for( i=1, k=-1, U[0]=-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;
	}
}

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