Cod sursa(job #2853107)

Utilizator Radu_marioRadu Mario Radu_mario Data 19 februarie 2022 21:30:54
Problema Potrivirea sirurilor Scor 66
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;

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

string A, B;
vector<int> AP;

constexpr int MOD = 101, MAX = 125;
int i, j, CNT;

void RabinKarp(string PAT, string TXT)
{
	size_t M = PAT.length();
	size_t N = TXT.length();
	long long P = 0, T = 0, H = 1;
	bool flag;

	for (i = 0; i < M - 1; ++i)
		H = (H * MAX) % MOD;

	for (i = 0; i < M; ++i)
	{
		P = (MAX * P + PAT[i]) % MOD;
		T = (MAX * T + TXT[i]) % MOD;
	}

	for (i = 0; i <= N - M; ++i)
	{
		if (P == T)
		{
			for (j = 0; j < M; ++j)
				if (TXT[i + j] != PAT[j]) break;
			if (j == M)
			{
				++CNT;
				if(CNT <= 1000) AP.push_back(i);
			}
		}
		if (i < N - M)
		{
			T = (MAX * (T - TXT[i] * H) + TXT[i + M]) % MOD;
			if (T < 0) T += MOD;
		}
	}
}

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

	file_out << CNT << '\n';
	for (auto it : AP) file_out << it << ' ';

	return 0;
}