Cod sursa(job #3205402)

Utilizator AndreasBossGamerBaragau Andreas AndreasBossGamer Data 19 februarie 2024 15:06:20
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <queue>
#include <string>
#define PUTERE 31
#define PUTERE2 29
#define MOD 100007

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

string s1, s2;
queue<int> rez;
int cnt = 0;

int main()
{
	///citire
	cin >> s1 >> s2;

	///daca primul string este mai lung
	if (s1.size() > s2.size())
	{
		cout << 0;
		return 0;
	}

	///calculez hash urile la primul sir
	int hashPrim1 = 0, hashPrim2 = 0;
	int hashSecund1 = 0, hashSecund2 = 0;
	int size1 = s1.size();
	for (int i = 0; i < size1; i++) {
		hashPrim1 += (s1[i] * PUTERE) % MOD;
		hashPrim2 += (s1[i] * PUTERE2) % MOD;
		hashSecund1 += (s2[i] * PUTERE) % MOD;
		hashSecund2 += (s2[i] * PUTERE2) % MOD;
	}
	if (hashPrim1 == hashSecund1 && hashPrim2 == hashSecund2)
	{
		rez.push(1);
		cnt++;
	}
	for (int i = size1; i < s2.size(); i++)
	{
		hashSecund1 = (hashSecund1 - ((s2[i - size1] * PUTERE) % MOD) + (s2[i] * PUTERE) % MOD) % MOD;
		hashSecund2 = (hashSecund2 - ((s2[i - size1] * PUTERE2) % MOD) + (s2[i] * PUTERE2) % MOD) % MOD;
		if (hashPrim1 == hashSecund1 && hashPrim2 == hashSecund2)
		{
			rez.push(i + 1 - size1);
			cnt++;
		}
	}

	cout << cnt << '\n';
	while (!rez.empty()) {
		cout << rez.front() << " ";
		rez.pop();
	}
}