Cod sursa(job #2876182)

Utilizator NFJJuniorIancu Ivasciuc NFJJunior Data 23 martie 2022 09:29:28
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("date.in");
ofstream g("date.out");
#define cin f
#define cout g
const int MOD = 1e9 + 7;

int main()
{
	string a, b;
	int ans = 0, hash_a = 0, hash = 0, power = 1;
	vector < int > poz;
	cin >> a >> b;
	for(int i=1;i<a.size();i++)
		power = (power * 26) % MOD;
	for(int i=0;i<a.size();i++)
		hash_a = (hash_a * 26 + a[i]) % MOD;
	for(int i=0;i<a.size();i++)
		hash = (hash * 26 + b[i]) % MOD;
	if(hash == hash_a)
	{
		ans ++;
		poz.push_back(0);
	}
	for(int i=a.size();i<b.size();i++)
	{
		hash = (hash - (power * b[i - a.size()] % MOD) + MOD) % MOD;
		hash = (hash * 26 + b[i]) % MOD;
		if(hash == hash_a)
		{
			ans ++;
			poz.push_back(i-a.size()+1);
		}
	}
	cout<<ans<<'\n';
	for(auto it : poz)
		cout<<it<<" ";
	return 0;
}