Cod sursa(job #2862523)

Utilizator QwertyDvorakQwerty Dvorak QwertyDvorak Data 5 martie 2022 14:38:28
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair

using ll = long long;

const string myf = "strmatch";
ifstream fin(myf + ".in");
ofstream fout(myf + ".out");

string a, b;
vector<int> poz;
inline int conv(char c) {
	if (islower(c))
		return c - 'a' + 1;
	return c - 'A' + 26 + 1;
}
vector<int> rabin_karp(const string &pat, const string &t) {
	const int p = 53; // larger than alphabet
	const int mod = 1e9 + 9;
	int patHash = 0;
	int np = pat.size();
	int nt = t.size();
	vector<int> poz;
	vector <long  long> ppow(max(np, nt));
	vector <long long> hashes(nt + 1, 0);

	ppow[0] = 1;
	for (int i = 1; i < (int)ppow.size(); ++i)
		ppow[i] = (ppow[i - 1] * p) % mod;

	for (int i = 0; i < nt; ++i)
		hashes[i + 1] = (hashes[i] + conv(t[i]) * ppow[i]) % mod;

	for (int i = 0; i < np; ++i)
		patHash = (patHash + conv(pat[i]) * ppow[i]) % mod;
	for (int i = 0; i + np - 1 < nt; ++i) {
		ll cur_h = (hashes[i + np] + mod - hashes[i]) % mod;
		if (cur_h == patHash * ppow[i] % mod)
			poz.pb(i);
	}
	return poz;

}

int main() {

	fin >> a >> b;
	vector<int> poz;
	poz = rabin_karp(a, b);
	fout << poz.size() << '\n';
	for (int i = 0; i < min((int)poz.size(), 1001); ++i)
		fout << poz[i] << " ";
	fin.close();
	fout.close();
	return 0;
}