Cod sursa(job #2791513)

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

#define MOD 1000000009
#define BASE 293

long long int hash1;
std::vector <long long int> hash2;
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 put = 1;
	fin >> str1 >> str2;
	hash2.resize(str2.size() + 1);
	if (str2.size() < str1.size()) {
		fout << "0";
		return 0;
	}
	hash1 = 0;
	for (int index = str1.size() - 1; index >= 0; index--) {
		hash1 *= BASE;
		hash1 += str1[index];
		hash1 %= MOD;
		put *= BASE;
		put %= MOD;
	}
	hash2[str2.size()] = 0;
	for (int index = str2.size() - 1; index >= 0; index--) {
		hash2[index] = hash2[index + 1] * BASE + str2[index];
		hash2[index] %= MOD;
	}
	for (int index = 0; index <= str2.size() - str1.size(); index++) {
		if (hash1 == (hash2[index] + MOD - (hash2[index + str1.size()] * put) % MOD) % MOD) {
			ans[cnt] = index;
			cnt++;
		}
		if (cnt == 1000) {
			break;
		}
	}
	fout << cnt << '\n';
	for (int index = 0; index < cnt; index++) {
		fout << ans[index] << ' ';
	}
	return 0;
}