Cod sursa(job #2142213)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 24 februarie 2018 20:58:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>

#define NMAX 2000005
#define MOD1 1000003
#define MOD2 10003
#define base 73

using namespace std;

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

int main() {
	int limit, N;
	int power1 = 1, power2 = 1;
	int strHash1 = 0, strHash2 = 0;
	int patternHash1 = 0, patternHash2 = 0;
	
	vector <int> sol;
	string text, pattern;

	fin >> pattern >> text;
	N = pattern.size();

	for (int i = 0; i < N; ++i) {
		patternHash1 = (patternHash1 * base + pattern[i] * base) % MOD1;
		patternHash2 = (patternHash2 * base + pattern[i] * base) % MOD2;

		strHash1 = (strHash1 * base + text[i] * base) % MOD1;
		strHash2 = (strHash2 * base + text[i] * base) % MOD2;

		power1 = (power1 * base) % MOD1;
		power2 = (power2 * base) % MOD2;
	}

	if (strHash1 == patternHash1 && strHash2 == patternHash2) {
		sol.push_back(0);
	}

	for (int i = N; i < (int)text.size(); ++i) {
		strHash1 = ((strHash1 - (power1 * text[i - N]) % MOD1 + MOD1) * base + text[i] * base) % MOD1;
		strHash2 = ((strHash2 - (power2 * text[i - N]) % MOD2 + MOD2) * base + text[i] * base) % MOD2;
	
		if (strHash1 == patternHash1 && strHash2 == patternHash2) {
			sol.push_back(i - N + 1);
		}
	}

	limit = min((int)sol.size(), 1000);
	fout << sol.size() << '\n';
	for (int i = 0; i < limit; ++i) {
		fout << sol[i] << ' ';
	}

	return 0;
}