Cod sursa(job #2105060)

Utilizator trifangrobertRobert Trifan trifangrobert Data 12 ianuarie 2018 16:12:38
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
// Rabin Karp

//#include <iostream>
//#include <conio.h>
#define X 73
#define Y 29
#define MOD1 666013
#define MOD2 777013
#define DIM 2000010

#include <cstring>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int hashA1 = 0;
int hashA2 = 0;
int hashB1 = 0;
int hashB2 = 0;
int power1 = 1;
int power2 = 1;
char a[DIM], b[DIM];
bool match[DIM];
int cnt = 0;
int lengthA, lengthB;

void Read()
{
	ifstream fin("strmatch.in");
	fin >> a >> b;
	fin.close();
}

void Solve()
{
	lengthA = (int)strlen(a);
	lengthB = (int)strlen(b);
	if (lengthA > lengthB)
		return;
	for (int i = 0;i < lengthA;++i)
	{
		hashA1 = (hashA1 + a[i]) * X % MOD1;
		hashA2 = (hashA2 + a[i]) * Y % MOD2;
		power1 = power1 * X % MOD1;
		power2 = power2 * Y % MOD2;
	}
	for (int i = 0;i < lengthA;++i)
	{
		hashB1 = (hashB1 + b[i]) * X % MOD1;
		hashB2 = (hashB2 + b[i]) * Y % MOD2;
	}
	if (hashA1 == hashB1 && hashA2 == hashB2)
	{
		match[0] = true;
		++cnt;
	}
	for (int i = lengthA;i < lengthB;++i)
	{
		hashB1 = hashB1 - 1LL * b[i - lengthA] * power1 % MOD1;
		hashB2 = hashB2 - 1LL * b[i - lengthA] * power2 % MOD2;
		while (hashB1 < 0)
			hashB1 += MOD1;
		while (hashB2 < 0)
			hashB2 += MOD2;
		hashB1 = (hashB1 + b[i]) * X % MOD1;
		hashB2 = (hashB2 + b[i]) * Y % MOD2;
		if (hashA1 == hashB1 && hashA2 == hashB2)
		{
			match[i - lengthA + 1] = true;
			++cnt;
		}
	}
}

void Write()
{
	ofstream fout("strmatch.out");
	int dim = min(1000, cnt);
	fout << cnt << "\n";
	cnt = 0;
	for (int i = 0;i < lengthB && cnt <= 1000;++i)
		if (match[i])
		{
			fout << i << " ";
			++cnt;
		}
	fout.close();
}

int main()
{
	Read();
	Solve();
	Write();
	//_getch();
	return 0;
}