Cod sursa(job #2104680)

Utilizator trifangrobertRobert Trifan trifangrobert Data 12 ianuarie 2018 04:52:37
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
// Rabin Karp

//#include <iostream>
//#include <conio.h>
#define X 97
#define Y 113
#define MOD1 666013
#define MOD2 777013

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

using namespace std;

string a, b;
vector <int> v;
int hashA1 = 0;
int hashA2 = 0;
int hashB1 = 0;
int hashB2 = 0;
int power1 = 1;
int power2 = 1;

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

void Repair1(int &x)
{
	while (x < 0)
		x += MOD1;
}

void Repair2(int &x)
{
	while (x < 0)
		x += MOD2;
}

void Solve()
{
	int lengthA = (int)a.length();
	int lengthB = (int)b.length();
	if (lengthA > lengthB)
		return;
	for (int i = 0;i < lengthA;++i)
	{
		hashA1 = (1LL * hashA1 * X % MOD1 + (int)a[i] * X) % MOD1;
		hashA2 = (1LL * hashA2 * Y % MOD2 + (int)a[i] * Y) % MOD2;
	}
	for (int i = 0;i < lengthA;++i)
	{
		hashB1 = (1LL * hashB1 * X % MOD1 + (int)b[i] * X) % MOD1;
		hashB2 = (1LL * hashB2 * Y % MOD2 + (int)b[i] * Y) % MOD2;
	}
	if (hashA1 == hashB1 && hashA2 == hashB2)
		v.push_back(0);
	for (int i = 1;i <= lengthA;++i)
	{
		power1 = 1LL * power1 * X % MOD1;
		power2 = 1LL * power2 * Y % MOD2;
	}
	for (int i = lengthA;i < lengthB;++i)
	{
		hashB1 = (1LL * hashB1 - (int)b[i - lengthA] * power1 % MOD1) % MOD1;
		hashB2 = (1LL * hashB2 - (int)b[i - lengthA] * power2 % MOD2) % MOD2;
		Repair1(hashB1);
		Repair2(hashB2);
		hashB1 = (1LL * hashB1 + (int)b[i]) * X % MOD1;
		hashB2 = (1LL * hashB2 + (int)b[i]) * Y % MOD2;
		if (hashA1 == hashB1 && hashA2 == hashB2)
			v.push_back(i - lengthA + 1);
	}
}

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

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