Cod sursa(job #2791556)

Utilizator cezar_titianuTitianu Cezar cezar_titianu Data 30 octombrie 2021 18:33:19
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <string>
#include <vector>

#define MOD1 1000000009
#define MOD2 1000000007
#define BASE 293

long long int hash11, hash12;
std::vector <long long int> hash21;
std::vector <long long int> hash22;

int ans[1005];

int main() {
	std::ifstream fin("strmatch.in");
	std::ofstream fout("strmatch.out");
	std::string str1, str2;
	int cnt = 0;
	long long int put1 = 1, put2 = 1;
	fin >> str1 >> str2;
	hash21.resize(str2.size() + 1);
	hash22.resize(str2.size() + 1);
	if (str2.size() < str1.size()) {
		fout << "0";
		return 0;
	}
	hash11 = 0;
	hash12 = 0;
	for (int index = str1.size() - 1; index >= 0; index--) {
		hash11 *= BASE;
		hash11 += str1[index];
		hash11 %= MOD1;
		hash12 *= BASE;
		hash12 += str1[index];
		hash12 %= MOD2;
		put1 *= BASE;
		put1 %= MOD1;
		put2 *= BASE;
		put2 %= MOD2;
	}
	hash21[str2.size()] = 0;
	hash22[str2.size()] = 0;
	for (int index = str2.size() - 1; index >= 0; index--) {
		hash21[index] = hash21[index + 1] * BASE + str2[index];
		hash21[index] %= MOD1;
		hash22[index] = hash22[index + 1] * BASE + str2[index];
		hash22[index] %= MOD2;
	}
	for (int index = 0; index <= str2.size() - str1.size(); index++) {
		if (hash11 == (hash21[index] + MOD1 - (hash21[index + str1.size()] * put1) % MOD1) % MOD1 && 
			hash12 == (hash22[index] + MOD2 - (hash22[index + str1.size()] * put2) % MOD2) % MOD2) {
			ans[cnt] = index;
			cnt++;
		}
		if (cnt == 1000) {
			break;
		}
	}
	fout << cnt << '\n';
	for (int index = 0; index < cnt; index++) {
		fout << ans[index] << ' ';
	}
	return 0;
}