Cod sursa(job #478503)

Utilizator Programmer01Mierla Laurentiu Marian Programmer01 Data 18 august 2010 22:17:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<stdio.h>
#include<string.h>

char *A, *B;
int *p, *matchPos, lengthA, lengthB, lengthMatch;

void prefix(){
	int k = -1;
	p[0] = -1;
	for(int i=1; i<lengthA; i++) {
		while(k >= 0 && A[i] != A[k+1])
			k = p[k];
		if(A[k+1] == A[i]) ++k;
		p[i] = k;
	}
}

void match(){
	prefix();

	int q = -1;
	for(int i=0; i<lengthB; i++){
		while(q+1 == lengthA || (q >= 0 && A[q+1] != B[i]))
			q = p[q];
		if(A[q+1] == B[i]) ++q;
		if(q == lengthA - 1)
			if(lengthMatch < 1000) matchPos[lengthMatch++] = i - lengthA + 1;
			else ++lengthMatch;
	}
}

void read(){
	FILE *ifile;

	A = new char[2000000];
	B = new char[2000000];
	p = new int[2000000];
	matchPos = new int[1000];

	ifile = fopen("strmatch.in", "r");
	fscanf(ifile, "%s", A);
	fscanf(ifile, "%s", B);
	lengthA = strlen(A);
	lengthB = strlen(B);

	fclose(ifile);
}

void write(){
	FILE *ofile;

	ofile = fopen("strmatch.out", "w");
	fprintf(ofile, "%i\n", lengthMatch);
	if(lengthMatch > 1000) lengthMatch = 1000;
	for(int i=0; i<lengthMatch; i++)
		fprintf(ofile, "%i ", matchPos[i]);

	fclose(ofile);
}


int main()
{
	read();
	match();
	write();
	return 0;
}