Cod sursa(job #2675490)

Utilizator mvcl3Marian Iacob mvcl3 Data 21 noiembrie 2020 21:02:14
Problema Potrivirea sirurilor Scor 26
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <string>
#include <iostream>
#include <vector>


const int base = 256;
const int mod = 101;

std::vector<int> rabin_karp(const std::string& A, const std::string& B)
{
	std::vector<int> sol;
	
	int refHash = 0;
	int currHash = 0;
	for (int i = 0; i < A.length(); ++i)
	{
		refHash = (refHash * base + A[i]) % mod;
		currHash = (currHash * base + B[i]) % mod;
	}

	int h = 1;
	for (int i = 0; i < A.length() - 1; ++i)
	{
		h = (h * base) % mod;
	}

	for (int i = 0; i <= B.length() - A.length(); ++i)
	{
		if(currHash == refHash && A == B.substr(i, A.length()))
		{
			sol.push_back(i);
		}

		currHash = (((currHash - h * B[i]) * base + B[i + A.length()]) % mod + mod) % mod;
	}

	return std::move(sol);
}



int main()
{
	std::ifstream in("strmatch.in");
	std::ofstream out("strmatch.out");

	std::string A, B;
	in >> A >> B;

	auto sol = rabin_karp(A, B);
	
	out << sol.size() << std::endl;
	for (const auto& idx : sol)
	{
		out << idx << ' ';
	}


	return 0;
}