Cod sursa(job #1278731)

Utilizator evodaniVasile Daniel evodani Data 29 noiembrie 2014 12:26:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <cstring>
using namespace std;
FILE *fin, *fout;

#define NMAX 2000001
#define MOD1 100007
#define MOD2 100021
#define P 73

char A[NMAX], B[NMAX];

int main() {
	fin = fopen ("strmatch.in", "r");
	fout = fopen ("strmatch.out", "w");

	int i, la, lb;
	int hashA1=0, hashA2=0, hashB1=0, hashB2=0, P1 = 1, P2 = 1;
	int matches = 0, match[NMAX];

	fscanf (fin, "%s%s", A, B);
	la = strlen(A); lb = strlen(B);

	if (la > lb) {
		fprintf(fout, "0\n");
		return 0;
	}

	for (i=0; i<la; ++i) {
		hashA1 = (P * hashA1 + A[i]) % MOD1;
		hashA2 = (P * hashA2 + A[i]) % MOD2;

		hashB1 = (P * hashB1 + B[i]) % MOD1;
		hashB2 = (P * hashB2 + B[i]) % MOD2;

		if (i) {
			P1 = (P1 * P) % MOD1;
			P2 = (P2 * P) % MOD2;
		}
	}

	if (hashA1 == hashB1 && hashA2 == hashB2) match[++matches] = 0;

	for (i=la; i<lb; ++i) {
		hashB1 = (((hashB1 - P1 * B[i-la]) % MOD1 + MOD1) * P + B[i]) % MOD1;
		hashB2 = (((hashB2 - P2 * B[i-la]) % MOD2 + MOD2) * P + B[i]) % MOD2;

		if (hashA1 == hashB1 && hashA2 == hashB2)  match[++matches] = i - la + 1;
	}

	fprintf (fout, "%d\n", matches);
	la = (matches < 1000)?matches:1000;
	for (i=1; i<=la; ++i) fprintf (fout, "%d ", match[i]);

	fclose(fin); fclose(fout);
	return 0;
}