Cod sursa(job #2647419)

Utilizator llama27Asd asd llama27 Data 4 septembrie 2020 15:34:55
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <random>

using namespace std;

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

#define MOD 133713

vector<string> table[MOD + 1];
string substring, myString;
int ssHash = 0;

int GetHash(string s)
{
	int key = 0;
	for (auto const& c : s)
		key += (int)c;

	key <<= 1;
	key %= MOD;
	key <<= 13;
	key %= MOD;
	key <<= 9;
	key %= MOD;
	key >>= 5;
	key %= MOD;
	key <<= 11;

	return key % MOD;
}

void Insert(string s)
{
	int pos = GetHash(s);
	table[pos].push_back(s);
}

void Delete(string s)
{
	int pos = GetHash(s);

	int i = 0;
	for (auto const& it : table[pos])
	{
		if (s.compare(it) == 0)
		{
			table[pos].erase(table[pos].begin() + i);
		}
		++i;
	}

}

bool Search(string s)
{
	int hash = GetHash(s);

	if (hash == ssHash)
	{
		for (const auto& it : table[hash])
		{
			if (s.compare(it) == 0)
			{
				Delete(it);
				return true;
			}
		}
	}
	return false;
}

int main()
{
	getline(in, substring);
	getline(in, myString);
	ssHash = GetHash(substring);

	string s;
	for (int i = 0; i < myString.size() - 2; i++)
	{
		for (int k = 0; k < 3; k++)
			s.push_back(myString[i + k]);
		Insert(s);
		s.clear();
	}


	vector<int> positions;
	int cnt = 0;
	for (int i = 0; i < myString.size() - 2; i++)
	{
		for (int k = 0; k < 3; k++)
			s.push_back(myString[i + k]);

		if (Search(s))
		{
			if (cnt <= 1000)
				positions.push_back(i);
			++cnt;
		}
		s.clear();
	}
	out << cnt << '\n';
	for (auto const& it : positions)
		out << it << ' ';
}