Cod sursa(job #934475)

Utilizator deividFlorentin Dumitru deivid Data 30 martie 2013 17:57:40
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 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,first;
int nrsol,sol[lim+5],Z[maxdim];
char A[maxdim<<1];

int main () {
	
	fscanf(f,"%s",A+1); n = strlen(A+1); first = n;
	A[n+1] = '#';
	fscanf(f,"%s",A+n+2);
	n = strlen(A+1);
	
	int L = 0,R = 0;
	for ( int i = 2 ; i <= n ; ++i ){
		
		if ( i > R ){
			for ( L = i , R = i-1 ; A[R+1] == A[R-L+2] ; ++R );
			Z[i] = R-L+1;
		}
		else{
			int k = i-L+1;
			if ( Z[k] < R-i+1 ){
				Z[i] = Z[k];
			}
			else{
				for ( L = i ; A[R+1] == A[R-L+2] ; ++R );
				Z[i] = R-L+1;
			}
		}
		
		if ( Z[i] == first ){
			++nrsol;
			if ( nrsol <= lim )	sol[nrsol] = i-first-2;
		}
	}
	
	fprintf(g,"%d\n",nrsol);
	for ( int i = 1 ; i <= nrsol && i <= lim ; ++i ){
		fprintf(g,"%d ",sol[i]);
	}
	fprintf(g,"\n");
	
	fclose(f);
	fclose(g);
	
	return 0;
}