Cod sursa(job #3030607)

Utilizator AndreiMLCChesauan Andrei AndreiMLC Data 17 martie 2023 19:09:20
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 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;
int calc(int n,int baza, int mod)
{
	int x=0;
	for (int i = 0; i < n; i++)
	{
		x = x * baza + s[i];
		x %= mod;
	}
	return x;
}

int main()
{
	f >> s >> a;
	int m = s.size();
	int n = a.size();
	int h1 = calc(m,baza1,mod1);
	int h2= calc(m, baza2, mod2);
	int h3 = 0;
	int h4 = 0;
	int 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 (h3 < 0)
			{
				h3 += 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] << ' ';
	}
}