Cod sursa(job #2809763)

Utilizator Radu_marioRadu Mario Radu_mario Data 27 noiembrie 2021 16:08:44
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include<bits/stdc++.h>
using namespace std;

ifstream file_in("strmatch.in");
ofstream file_out("strmatch.out");

char A[2000005], B[2000005];
long long N, P[1005];

struct Hash
{
	long long base, modulo, power, value;
	Hash(int b, int m) { base = b, modulo = m, power = 0, value = 0; }

	void init(char* S, int length)
	{
		power = 1, value = 0;
		for (int i = length - 1; i >= 0; --i)
		{
			value = (value + (1LL * power * S[i]) % modulo) % modulo;
			if (i) power = (power * base) % modulo;
		}
	}

	void roll(char toRemove, char toAdd)
	{ value = (((value - (1LL * toRemove * power) % modulo + modulo) * base) % modulo + toAdd) % modulo; }

	bool operator==(const Hash& other) const 
	{ return value == other.value; }
};

int main()
{
	file_in >> A >> B;

	int length_A = strlen(A);
	int length_B = strlen(B);

	Hash hash_A1{ 257, (int)2e9 + 7 }, hash_B1{ 257, (int)2e9 + 7 };
	Hash hash_A2{ 263, (int)2e9 + 9 }, hash_B2{ 263, (int)2e9 + 9 };

	hash_A1.init(A, length_A); hash_B1.init(B, length_A);
	hash_A2.init(A, length_A); hash_B2.init(B, length_A);

	if (hash_A1.value == hash_B1.value && hash_A2.value == hash_B2.value) 
		++N;

	for (int i = length_A; i < length_B; ++i)
	{
		hash_B1.roll(B[i - length_A], B[i]);
		hash_B2.roll(B[i - length_A], B[i]);

		if (hash_A1.value == hash_B1.value && hash_A2.value == hash_B2.value)
		{
			if (N <= 1000) P[++N] = i - length_A + 1;
			else ++N;
		}
	}

	file_out << N << '\n';
	if (N > 1000) N = 1000;
	for (int i = 1; i <= N; ++i) file_out << P[i] << ' ';

	return 0;
}