Cod sursa(job #2876560)

Utilizator NFJJuniorIancu Ivasciuc NFJJunior Data 23 martie 2022 12:18:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define cin f
#define cout g

const int MOD1 = 100007;
const int MOD2 = 100021;
const int p = 26;

int main()
{
	string a, b;
	cin >> a >> b;
	int lna, lnb;
	lna = a.size(), lnb = b.size();
	int hash1_a = 0, hash2_a = 0;
	int p1 = 1, p2 = 1;
	for(int i=0;i<lna;i++)
	{
		hash1_a = (hash1_a * p + a[i]) % MOD1;
		hash2_a = (hash2_a * p + a[i]) % MOD2;
		if(i != 0)
		{
			p1 = (p1 * p) % MOD1;
			p2 = (p2 * p) % MOD2;
		}
	}
	if(lna > lnb)
	{
		cout<<0<<'\n';
		return 0;
	}
	int hash1 = 0, hash2 = 0;
	for(int i=0;i<lna;i++)
	{
		hash1 = (hash1 * p + b[i]) % MOD1;
		hash2 = (hash2 * p + b[i]) % MOD2;
	}
	int ans = 0;
	vector < int > poz;
	poz.reserve(lnb);
	if(hash1 == hash1_a and hash2 == hash2_a)
		poz[ans ++] = 0;
	for(int i=lna;i<lnb;i++)
	{
		hash1 = ((hash1 - (b[i - lna] * p1) % MOD1 + MOD1) * p + b[i]) % MOD1;
		hash2 = ((hash2 - (b[i - lna] * p2) % MOD2 + MOD2) * p + b[i]) % MOD2;
		if(hash1 == hash1_a and hash2 == hash2_a)
			poz[ans ++] = i - lna + 1;
	}
	cout<<ans<<'\n';
	for(int i=0;i<ans;i++)
		cout<<poz[i]<<" ";
	return 0;
}