Cod sursa(job #769443)

Utilizator cvicentiuCiorbaru Vicentiu Marian cvicentiu Data 19 iulie 2012 13:13:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <stdio.h>
#include <string.h>
#define MOD1 1000007
#define MOD2 1000021
#define BASE 73
#define MAXL 2000001
char A[MAXL], B[MAXL];
bool match[MAXL];
int main() {
	
	FILE *f = fopen("strmatch.in", "r");
	FILE *g = fopen("strmatch.out", "w");

	fscanf(f, "%s %s", A, B);


	int lenA = strlen(A), lenB = strlen(B);

	if (lenA > lenB) {
		fprintf(g, "0");
		fclose(f);
		fclose(g);
		return 0;
		
	}
	int count = 0;
	int hashA1, hashA2; //valorile hash ale substringului;
	int hash1, hash2;  //valorile hash ale substringului de lungime
			   //lenA din B
	hashA1 = 0, hashA2 = 0, hash1 = 0, hash2 = 0;

	int maxPow1 = 1, maxPow2 = 1;
	for (int i = 0; i < lenA; i++) {
		hashA1 = (hashA1 * BASE + A[i]) % MOD1;
		hashA2 = (hashA2 * BASE + A[i]) % MOD2;
		hash1 = (hash1 * BASE + B[i]) % MOD1;
		hash2 = (hash2 * BASE + B[i]) % MOD2;
		if (i != 0) {
			maxPow1 = (maxPow1 * BASE) % MOD1;
			maxPow2 = (maxPow2 * BASE) % MOD2;
		}
	}

	if (hash1 == hashA1 && hash2 == hashA2) {
		count++;
		match[0] = true;
	}

	for (int i = lenA; i < lenB; i++) {
		hash1 = ((hash1 - (B[i - lenA] * maxPow1) % MOD1 + MOD1) * BASE + B[i]) % MOD1;
		hash2 = ((hash2 - (B[i - lenA] * maxPow2) % MOD2 + MOD2) * BASE + B[i]) % MOD2;
		if (hashA1 == hash1 && hashA2 == hash2) {
			count++;
			match[i - lenA + 1] = true;
		}
	}

	fprintf(g, "%d\n", count);
	count = 0;
	for (int i = 0; i < lenB && count < 1000; i++) {
		if (match[i] == true) {
			count++;
			fprintf(g, "%d ", i);
		}
	}
	
	fclose(f);
	fclose(g);
	return 0;

}