Cod sursa(job #3030614)

Utilizator AndreiMLCChesauan Andrei AndreiMLC Data 17 martie 2023 19:13:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <vector>
#define baza1 256
#define baza2 300
#define mod2 1000000080
#define mod1 1000000007

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

string s, a;
int tot;
vector<int>v;

long long calc(long long n,int baza, int mod)
{
	long long x=0;
	for (int i = 0; i < n; i++)
	{
		x = x * baza + s[i];
		x %= mod;
	}
	return x;
}

int main()
{
	f >> s >> a;
	long long m = s.size();
	long long n = a.size();
	long long h1 = calc(m,baza1,mod1);
	long long h2= calc(m, baza2, mod2);
	long long h3 = 0;
	long long h4 = 0;
	long long put1 = 1, put2 = 1;
	for (int i = 0; i < m; i++)
	{
		put1 *= baza1;
		put1 %= mod1;
		put2 *= baza2;
		put2 %= mod2;
	}
	for (int i = 0; i < n; i++)
	{
		h3 = baza1 * h3 + a[i];
		h3 %= mod1;
		h4 = baza2 * h4 + a[i];
		h4 %= mod2;
		if (i >= m)
		{
			h3 = h3 - (a[i - m] * put1) % mod1;
			if (h3 < 0)
			{
				h3 += mod1;
			}
			h4 = h4 - (a[i - m] * put2) % mod2;
			h4 %= mod2;
			if (h4 < 0)
			{
				h4 += mod2;
			}
		}
		if (i >= m-1)
		{
			if (h1 == h3 && h2==h4)
			{
				tot++;
				v.push_back(i - m + 1);
			}
		}
	}
	g << tot << '\n';
	int lung = min(1000, (int)v.size());
	for (int i = 0; i <= lung - 1; i++)
	{
		g << v[i] << ' ';
	}
}