Cod sursa(job #2080610)

Utilizator ice_creamIce Cream ice_cream Data 3 decembrie 2017 12:50:54
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

ifstream f ("strmatch.in");
ofstream g ("strmatch.out");

const int B = 127;
const int NMAX = 2000000;

int n, m;
char a[NMAX + 1];
char b[NMAX + 1];
vector <int> sol;

void citeste() {
	f >> a >> b;
	n = strlen(a);
	m = strlen(b);
}

unsigned long long get_hash(int n, char *s) {
	unsigned long long h = 0;
	unsigned long long b = 1;
	for (int i = 0; i < n; i++) {
		h = h + b * s[i];
		b = b * B;
	}
	return h;
}

void rolling_hash() {
	unsigned long long h = get_hash(n, a);
	unsigned long long current_h = get_hash(n, b);

	unsigned long long b_ = 1;
	for (int i = 1; i < n; i++) b_ = b_ * B;

	if (current_h == h) sol.push_back(0);
	for (int i = n; i < m; i++) {
		current_h = current_h / B + b_ * b[i];
		if (current_h == h) sol.push_back(i - n + 1);
		if (sol.size() > 1000) return;
	}
}

void scrie() {
	int l = sol.size();
	g << l << '\n';
	for (int i = 0; i < l; i++)
		g << sol[i] << ' ';
	g << '\n';
}

int main() {
	citeste();
	rolling_hash();
	scrie();
	return 0;
}