Cod sursa(job #896916)

Utilizator deividFlorentin Dumitru deivid Data 27 februarie 2013 17:53:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<stdio.h>
#include<cstring>

#define maxdim 2000005
#define lim 1000

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

int n,m;
int pi[maxdim],sol[lim+5];
char A[maxdim],B[maxdim];

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