Cod sursa(job #683330)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 20 februarie 2012 15:01:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<stdio.h>
#include<cstring>

#define maxdim 2000005

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

int n,m,matches;
int pi[maxdim],sol[1005];
char A[maxdim],B[maxdim];

inline void prefix () {
	
	n = strlen(A+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 = k + 1;
		}
		
		pi[i] = k;
	}
}

inline void kmp (){
	
	m = strlen(B+1);
	int q = 0;
	
	for ( int i = 1 ; i <= m ; ++i ){
		
		while ( q > 0 && B[i] != A[q+1] ){
			q = pi[q];
		}
		if ( B[i] == A[q+1] ){
			q = q + 1;
		}
		
		if ( q == n ){
			++matches;
			if ( matches <= 1000 ){
				sol[matches] = i - n;
			}
		}
	}
}

int main () {
	
	fscanf(f,"%s\n%s",A+1,B+1);
	
	prefix();
	kmp();
	
	fprintf(g,"%d\n",matches); 
	matches = matches <= 1000 ? matches : 1000;
	for ( int i = 1 ; i <= matches ; ++i ){
		fprintf(g,"%d ",sol[i]);
	}
	fprintf(g,"\n");
	
	fclose(f);
	fclose(g);
	
	return 0;
}