Cod sursa(job #144470)

Utilizator scvalexAlexandru Scvortov scvalex Data 27 februarie 2008 18:17:34
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <cstring>
#include <fstream>

using namespace std;

const int Factor = 73;
const int Mod1 = 100007;
const int Mod2 = 100021;

char P[2000000],
	 T[2000000];

int matched[2000000],
	mn(0);

FILE *fout;

void rkmatch() {
	int M = strlen(P),
		N = strlen(T);

	int ps1(0),
		ps2(0);
	int i;
	for (i = 0; i < M; ++i) {
		ps1 = (ps1 * Factor + P[i]) % Mod1;
		ps2 = (ps2 * Factor + P[i]) % Mod2;
	}
	//cout << ps1 << " - " << ps2 << endl;

	int raisedFactor1(1),
		raisedFactor2(1);
	for (i = 0; i < M - 1; ++i) {
		raisedFactor1 = (raisedFactor1 * Factor) % Mod1;
		raisedFactor2 = (raisedFactor2 * Factor) % Mod2;
	}

	int check1(0),
		check2(0);
	for (i = 0; i < M; ++i) {
		check1 = (check1 * Factor + T[i]) % Mod1;
		check2 = (check2 * Factor + T[i]) % Mod2;
	}
	if ((check1 == ps1) && (check2 == ps2))
		matched[mn++] = 0;

	for (; i < N; ++i) {
		check1 = (((check1 - T[i-M]*raisedFactor1) % Mod1 + Mod1) * Factor + T[i]) % Mod1;
		check2 = (((check2 - T[i-M]*raisedFactor2) % Mod2 + Mod2) * Factor + T[i]) % Mod2;

		//cout << check1 << " - " << check2 << endl;

		if ((check1 == ps1) && (check2 == ps2))
			matched[mn++] = i - M + 1;
	}

	fprintf(fout, "%d\n", mn);
	for (i = 0; i < ((mn > 1000) ? (1000) : (mn)); ++i)
		fprintf(fout, "%d ", matched[i]);
	fprintf(fout, "\n");
}

int main(int argc, char *argv[]) {
	FILE *fin = fopen("strmatch.in", "r");
	fscanf(fin, "%s", P);
	fscanf(fin, "%s", T);
	fclose(fin);

	fout = fopen("strmatch.out", "w");
	rkmatch();
	fclose(fout);

	return 0;
}