Cod sursa(job #840931)

Utilizator Brz_VladBrezae Vlad Brz_Vlad Data 23 decembrie 2012 15:24:28
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 1.35 kb
#include <stdio.h>
#include <string.h>

#define MAXN 2000000

char A[MAXN],B[MAXN];
int P[MAXN];
int m,n;

int solutions[1000];
int nr_sol=0;

// A[0:i]
// P[i] = greatest k (strictly lower than i ) 
// so that A[i-k:i] matches A[0:k]
// -1 if there is none
void computeDinamicA()
{
	int i;
	P[0] = -1;
	for(i=1;i<m;i++){
		if( A[i] == A[P[i-1]+1] )
			P[i] = P[i-1]+1;
		else{
			if( A[i] == A[0] )
				P[i] = 0;
			else
				P[i] = -1;
		}		
	}

//	FILE* prev = fopen("prev.txt","w");
//	for(i=0;i<m;i++)
//	  fprintf(prev,"%d : %d\n",i,P[i]);
//	fclose(prev);
}

int main(int argc, char* argv[])
{
	FILE *fin,*fout;
	fin = fopen("strmatch.in","r");
	fgets(A,MAXN,fin);
	fgets(B,MAXN,fin);
	fclose(fin);
	
	m = strlen(A)-1;
	n = strlen(B)-1;
	A[m] = 0;
	B[n] = 0;
//	printf("%d %d\n",m,n);
	
	computeDinamicA();

	int i,j=-1;
	for(i=0;i<n;i++){
//		printf("StartBi=%d, StartAj=%d, B[i]=%c,A[j+1]=%c ||| ",i,j,B[i],A[j+1]);
		if( B[i] == A[j+1] ){
			j++;
			if( j == m-1 ){
				if( nr_sol < 1000 )
					solutions[nr_sol] = i-m+1;
				nr_sol++;
				j = P[j];
			}
		}
		else if( j != -1 ){
			if( P[j] == -1 )
				j = -1;
			else
				j = P[j];
			i--;
		}
//		printf("Bi=%d, Aj=%d\n",i,j);	
	}

	fout = fopen("strmatch.out","w");
	fprintf(fout,"%d\n",nr_sol);
	if( nr_sol > 1000 )
		nr_sol = 1000;
	for(i=0;i<nr_sol;i++)
		fprintf(fout,"%d ",solutions[i]);

	fclose(fout);
	return 0;
}