Cod sursa(job #2423978)

Utilizator nicu97oTuturuga Nicolae nicu97o Data 22 mai 2019 13:28:02
Problema Potrivirea sirurilor Scor 24
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
#define N 1000

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int bernsteinHash(string key, int len);


int main() {
	string firstStr;
	getline(fin, firstStr);
	string secondStr;
	getline(fin, secondStr);
	int hasToCompare = bernsteinHash(firstStr, firstStr.length());
	int nrOfSolutions = 0;
	int sol[N];
	for (int i = 0; i < secondStr.length() - firstStr.length(); ++i) {
		if (hasToCompare == bernsteinHash(secondStr.substr(i, firstStr.length()), firstStr.length())) {
			if (nrOfSolutions < 1000) {
				sol[nrOfSolutions++] = i;
			}
			else {
				nrOfSolutions++;
			}
		}
	}
	fout << nrOfSolutions << '\n';
	for (int i = 0; i < nrOfSolutions; ++i) {
		fout << sol[i] << ' ';
	}
	return 0;
}

int bernsteinHash(string key, int len) {
	int h = 0;
	for (int i = 0; i < len; ++i) {
		h = 33 * h + key[i];
	}
	return h;
}