Cod sursa(job #574409)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 7 aprilie 2011 10:06:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<stdio.h>
#include<string>

#define maxL 2000005

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

int N,M,k,i,pi[maxL],NrSol,Sol[maxL];
char A[maxL],B[maxL];

int main () {
	
	fscanf(f,"%s%s",A+1,B+1);
	M = strlen(A+1); N = strlen(B+1);
	
	for ( i = 2 ; i <= M ; ++i ){
		while ( k > 0 && A[k+1] != A[i] )
			k = pi[k];
		if ( A[k+1] == A[i] )
			++k;
		pi[i] = k;
	}
	
	for ( i = 1 , k = 0 ; i <= N ; ++i ){
		while ( k > 0 && A[k+1] != B[i] )
			k = pi[k];
		if ( A[k+1] == B[i] )
			++k;
		if ( k == M ){
			++NrSol;
			if ( NrSol <= 1000 )
				Sol[NrSol] = i - M;
		}
	}
	
	fprintf(g,"%d\n",NrSol);
	
	if ( NrSol > 1000 )	NrSol = 1000;
	
	for ( i = 1 ; i <= NrSol ; ++i )
		fprintf(g,"%d ",Sol[i]);
	
	fclose(f);
	fclose(g);
	
	return 0;
}