Cod sursa(job #2104679)

Utilizator trifangrobertRobert Trifan trifangrobert Data 12 ianuarie 2018 04:47:14
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
// Rabin Karp

//#include <iostream>
//#include <conio.h>
#define X 97
#define MOD 666013

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

using namespace std;

string a, b;
vector <int> v;
int hashA = 0;
int hashB = 0;
int power = 1;

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

void Repair(int &x)
{
	while (x < 0)
		x += MOD;
}

void Solve()
{
	int lengthA = (int)a.length();
	int lengthB = (int)b.length();
	if (lengthA > lengthB)
		return;
	for (int i = 0;i < lengthA;++i)
		hashA = (1LL * hashA * X % MOD + (int)a[i] * X) % MOD;
	for (int i = 0;i < lengthA;++i)
		hashB = (1LL * hashB * X % MOD + (int)b[i] * X) % MOD;
	if (hashA == hashB)
		v.push_back(0);
	for (int i = 1;i <= lengthA;++i)
		power = 1LL * power * X % MOD;
	for (int i = lengthA;i < lengthB;++i)
	{
		hashB = (1LL * hashB - (int)b[i - lengthA] * power % MOD) % MOD;
		Repair(hashB);
		hashB = (1LL * hashB + (int)b[i]) * X % MOD;
		if (hashA == hashB)
			v.push_back(i - lengthA + 1);
	}
	//59323745 % 666013 == 485888
	//620994
	//6305
	//59.951.044
}

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;
}