Cod sursa(job #612831)

Utilizator pepeneportocala pepene Data 10 septembrie 2011 15:27:56
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.13 kb
#include <iostream>
#include <stdlib.h>
#include <fstream>

using namespace std;

const int  _MAX_LENGTH_ = 2000001;
const int NR_PRIM_1 = 13;
const int NR_PRIM_2 = 13;	//17;

const int NR_HASH_1 = 100007;//666203;
const int NR_HASH_2 = 100021;//1000001;

char a[_MAX_LENGTH_];
char b[_MAX_LENGTH_];

void read();
void solve();
void check();
void print();

int main()
{
	read();
	solve();
	check();
	print();

	return 0;
}

void read()
{
	ifstream ifs("strmatch.in", fstream::in);

	ifs >> a >> b;
};

int nr_sol;
int sol[10000];

void solve()
{
	freopen("strmatch.out", "w", stdout);

	int p1 = 1;
	int p2 = 1;
	int a_hash_1 = 0;
	int a_hash_2 = 0;
	int b_hash_1 = 0;
	int b_hash_2 = 0;
	int i, j;

	int strlen_a = 0;
	int strlen_b = 0;

	for (strlen_a = 0; a[strlen_a] != 0; ++strlen_a);
	for (strlen_b = 0; b[strlen_b] != 0; ++strlen_b);

	if (strlen_a > strlen_b) printf("0\n");

	for (int i = 0; i < strlen_a; ++i)
	{
		a_hash_1 = ((a_hash_1 * NR_PRIM_1) % NR_HASH_1 + a[i]) % NR_HASH_1;
		a_hash_2 = ((a_hash_2 * NR_PRIM_2) % NR_HASH_2 + a[i]) % NR_HASH_2;

		b_hash_1 = ((b_hash_1 * NR_PRIM_1) % NR_HASH_1 + b[i]) % NR_HASH_1;
		b_hash_2 = ((b_hash_2 * NR_PRIM_2) % NR_HASH_2 + b[i]) % NR_HASH_2;

		if (i == 0) continue;
		p1 = (p1 * NR_PRIM_1)% NR_HASH_1;
		p2 = (p2 * NR_PRIM_2)% NR_HASH_2;
	}

	if (a_hash_1 == b_hash_1 && a_hash_2 == b_hash_2)
		sol[++nr_sol] = 0;

	for (j = strlen_a; j < strlen_b; ++j)
	{
		b_hash_1 = b_hash_1 - (b[j-strlen_a] * p1) % NR_HASH_1 + NR_HASH_1;
		b_hash_2 = b_hash_2 - (b[j-strlen_a] * p2) % NR_HASH_2 + NR_HASH_2;

		b_hash_1 = b_hash_1 % NR_HASH_1;
		b_hash_2 = b_hash_2 % NR_HASH_2;

 		b_hash_1 = ((b_hash_1 * NR_PRIM_1) % NR_HASH_1 + b[j]) % NR_HASH_1;
		b_hash_2 = ((b_hash_2 * NR_PRIM_2) % NR_HASH_2 + b[j]) % NR_HASH_2; 
		
		if (a_hash_1 == b_hash_1 && a_hash_2 == b_hash_2)
			sol[++nr_sol] = j + 1 -strlen_a;
	}

	printf("%d\n", nr_sol);

	for (int i = 1; i <= 1000; ++i)
		printf("%d ", sol[i]);
};

void check()
{
};

void print()
{
	//ofstream ofs("strmatch.out", fstream::out);

	//ofs << a << "\n" << b << "\n";
};