Cod sursa(job #3277321)

Utilizator iccjocIoan CHELARU iccjoc Data 15 februarie 2025 18:33:27
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>
#define type int
using namespace std;

const type MOD = 1e9 + 7;
const type SIZE = 2000000;
type powers[SIZE + 1];
type hashes[SIZE + 1];
type base = 512;

void buildRollingHash(string text)
{
	type n = text.size();
	for(type i = n - 1; i >= 0; i--)
	{
		hashes[i] = ((1LL * hashes[i + 1] * base) % MOD + text[i]) % MOD;
	}
}

void buildPowerVector(string text)
{
	type n = text.size();
	powers[0] = 1;
	for(type i = 1; i <= n; i++)
	{
		powers[i] = (1LL * powers[i - 1] * base) % MOD;
	}
}

type buildHash(string text)
{
	type n = text.size();
	type hash = 0;
	for(type i = n - 1; i >= 0; i--)
	{
		hash = ((1LL * hash * base) % MOD + text[i]) % MOD;
	}
	return hash;
}

type retriveSequenceHashFromRollingHash(type left, type right)
{
	return (hashes[left] - (1LL * hashes[right + 1] * powers[right - left + 1]) % MOD) % MOD;
}

int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	string tbf, tbs;
	cin >> tbf >> tbs;
	buildRollingHash(tbs);
	buildPowerVector(tbs);
	int hash = buildHash(tbf);
	int cnt = 0;
	for(int i = 0; i + tbf.size() - 1 < tbs.size(); i++)
	{
		if(retriveSequenceHashFromRollingHash(i, i + tbf.size() - 1) == hash)
		{
			cnt++;
		}
	}
	cout << cnt << "\n";
	cnt = 0;
	for(int i = 0; i + tbf.size() - 1 < tbs.size(); i++)
	{
		if(cnt < 1000 && retriveSequenceHashFromRollingHash(i, i + tbf.size() - 1) == hash)
		{
			cout << i << " ";
			cnt++;
		}
	}
}