Cod sursa(job #2976943)

Utilizator PatruMihaiPatru Mihai PatruMihai Data 10 februarie 2023 13:49:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int MOD1 = 1e5 + 7;
const int MOD2 = 1e5 + 21;
const int BAZA = 73;

int match[2000001];

int main()
{
	string s1, s2;
	fin >> s1 >> s2;

	int n1 = s1.size();
	int n2 = s2.size();

	int hash1_1 = 0, hash1_2 = 0;
	int hash2_1 = 0, hash2_2 = 0;
	vector<int> v;

	if (n1 > n2)
	{
		fout << 0;
		return 0;
	}

	int baza1 = 1, baza2 = 1;

	for (int i = 0; i < n1; i++)
	{
		hash1_1 = (hash1_1 * BAZA + s1[i]) % MOD1;
		hash1_2 = (hash1_2 * BAZA + s1[i]) % MOD2;

		hash2_1 = (hash2_1 * BAZA + s2[i]) % MOD1;
		hash2_2 = (hash2_2 * BAZA + s2[i]) % MOD2;

		if (i != 0)
		{
			baza1 = (baza1 * BAZA) % MOD1;
			baza2 = (baza2 * BAZA) % MOD2;
		}
	}

	int nr = 0;
	if (hash1_1 == hash2_1 && hash1_2 == hash2_2)
	{
		match[0] = 1;
		nr++;
	}

	for (int i = n1; i < n2; i++)
	{
		hash2_1 = ((hash2_1 - (s2[i - n1] * baza1) % MOD1 + MOD1) * BAZA + s2[i]) % MOD1;
		hash2_2 = ((hash2_2 - (s2[i - n1] * baza2) % MOD2 + MOD2) * BAZA + s2[i]) % MOD2;

		if (hash2_1 == hash1_1 && hash2_2 == hash1_2)
		{
			match[i - n1 + 1] = 1;
			nr++;
		}
	}

	fout << nr << "\n";

	nr = 0;
	for (int i = 0; i < n2 && nr < 1000; i++)
	{
		if (match[i])
		{
			nr++;
			fout << i << " ";
		}
	}

	return 0;
}