Cod sursa(job #3205395)

Utilizator AndreasBossGamerBaragau Andreas AndreasBossGamer Data 19 februarie 2024 14:57:00
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <queue>
#include <string>
#define PUTERE 31
#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 hash1 = 0, hash2 = 0;
	int size1 = s1.size();
	for (int i = 0; i < size1; i++) {
		hash1 += (s1[i] * PUTERE) % MOD;
		hash2 += (s2[i] * PUTERE) % MOD;
	}
	if (hash1 == hash2)
	{
		rez.push(1);
		cnt++;
	}
	for (int i = size1; i < s2.size(); i++)
	{
		hash2 = (hash2 - ((s2[i - size1] * PUTERE) % MOD) + (s2[i] * PUTERE) % MOD) % MOD;
		if (hash1 == hash2)
		{
			rez.push(i + 1 - size1);
			cnt++;
		}
	}

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