Cod sursa(job #2739229)

Utilizator vali_27Bojici Valentin vali_27 Data 7 aprilie 2021 11:55:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>

std::ifstream f("strmatch.in");
std::ofstream g("strmatch.out");

typedef unsigned long long ULL;
const int MOD = 666013;
const int prime = 13;

unsigned hash(const std::string& s, int start, int end)
{
	unsigned h = 0, p = 1;
	for (int i = end; i>=start;--i)
	{
		h = (h + s[i] * p) % MOD;
		p = (p * prime) % MOD;
	}
	return h;
}
 

void find(const std::string& s, const std::string& pattern)
{
	int patSize = pattern.size();
	int sSize = s.size();
	int count = 0;
	int apar[1000];
	unsigned pathash = hash(pattern, 0, patSize - 1);
	unsigned shash = hash(s, 0, patSize  - 1);
	
	unsigned p = 1;
	for (int i = 1; i < patSize; i++)
		p = (p * prime) % MOD;
 
	for (int i = 0; i <= sSize - patSize; ++i)
	{
		if(i == 474)
		std::cout << pathash << ' ' << shash << '\n';
		if (pathash == shash)
		{
			 
			bool ok = true;
			for (int k = 0; ok && k < patSize; ++k)
				if (s[i + k] != pattern[k])ok = false;

			if (ok)
			{
				apar[count++] = i;
				if (count == 1000)
				{
					break;
				}
			}
		}
		if (i + patSize < sSize)
			shash = ((shash - (p * s[i]) % MOD + MOD) * prime + s[i + patSize]) % MOD;
		
	}
	g << count << '\n';
	for (int i = 0; i < count; ++i)
		g << apar[i] << ' ';
}

int main()
{
	std::string s, p;
	
	f >> p >> s;
	
	find(s, p);
}