Cod sursa(job #1904519)

Utilizator BonCipBonciocat Ciprian Mircea BonCip Data 5 martie 2017 16:45:04
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <stdio.h>

namespace Var {
	FILE *fin, *fout;
	int M, N;
	char *A, *B;
	int *pi, nsol, *sol;
};

void citire() {
	using namespace Var;
	A = new char[2000002];
	B = new char[2000002];
	while ((A[++M] = fgetc(fin)) != '\n');
	while ((B[++N] = fgetc(fin)) != '\n');
	--M;
	--N;
}
void prefix() {
	using namespace Var;
	pi = new int[M + 1]();
	int k = 0;
	for (int i = 2; i <= M; ++i) {
		while (A[k + 1] != A[i] && k > 0) {
			k = pi[k];
		}
		if (A[k + 1] == A[i]) {
			pi[i] = k + 1;
		} else {
			pi[i] = 0;
		}
	}
}
void kmp() {
	using namespace Var;
	sol = new int[1000];
	int k = 0;
	for (int i = 1; i <= N; ++i) {
		while (A[k + 1] != B[i] && k > 0) {
			k = pi[k];
		}
		if (A[k + 1] == B[i]) {
			k = k + 1;
		} else {
			k = 0;
		}
		if (k == M) {
			if (nsol < 1000) {
				sol[nsol] = i - M;
			}
			++nsol;
		}
	}
}
void afisare() {
	using namespace Var;
	fprintf(fout, "%d\n", nsol);
	for (int i = 0; i < nsol && i < 1000; ++i) {
		fprintf(fout, "%d ", sol[i]);
	}
	fprintf(fout, "\n");
}

int main()
{
	using namespace Var;
	fin = fopen("strmatch.in", "r");
	fout = fopen("strmatch.out", "w");
	
	citire();
	prefix();
	kmp();
	afisare();
	
	fclose(fin);
	fclose(fout);
	return 0;
}