Cod sursa(job #3298323)

Utilizator vladm98Munteanu Vlad vladm98 Data 28 mai 2025 19:54:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>

using namespace std;

int base = 512;
int MOD = 1000000007;
int rollingHash[2000005];
int bases[2000005];


int generateHash(string s) {
	// hash(s) = s[0] + s[1] * b + s[2] * b ^ 2 + ...

	int hash = 0;

	for (int i = (int) s.size() - 1; i >= 0; i--) {
		hash = (1LL * hash * base + s[i]) % MOD;
	}

	return hash;
}

void rollHash(string s) {
	for (int i = (int) s.size() - 1; i >= 0; i--) {
		rollingHash[i] = (1LL * rollingHash[i + 1] * base + s[i]) % MOD;
	}
}

int getHashInterval(int left, int right) {
	return ((rollingHash[left] - 1LL * rollingHash[right + 1] * bases[right - left + 1]) % MOD + MOD) % MOD;
}

void buildBases() {
	bases[0] = 1;
	for (int i = 1; i <= 2000000; ++i) {
		bases[i] = (1LL * bases[i - 1] * base) % MOD;
	}
}
int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	string s, t;

	cin >> s >> t;

	buildBases();
	int hash = generateHash(s);
	rollHash(t);

	int counter = 0;
	for (int i = 0; i + s.size() <= t.size(); ++i) {
		if (hash == getHashInterval(i, i + s.size() - 1)) {
			counter++;
		}
	}

	cout << counter << '\n';
	counter = 0;
	for (int i = 0; i + s.size() <= t.size() and counter < 1000; ++i) {
		if (hash == getHashInterval(i, i + s.size() - 1)) {
			counter++;
			cout << i << ' ';
		}
	}

	return 0;

}