#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include "message.h"
#include "poszukiwania.h"

using hash_t = unsigned long long;

const hash_t base_1 = 1738421; // CHANGE
const hash_t base_2 = 532603; // CHANGE


hash_t hash_f1(hash_t _old_hash, hash_t _old_value, hash_t _new_value)
{
	return (base_1 * (_old_hash - _old_value)) + _new_value;
}

hash_t hash_f2(hash_t _old_hash, hash_t _old_value, hash_t _new_value)
{
	return (base_2 * (_old_hash - _old_value)) + _new_value;
}



struct hash_data
{
	hash_t hash_1 = 0;
	hash_t pow_base_1 = 1;
	hash_t hash_2 = 0;
	hash_t pow_base_2 = 1;

	void send(int _target)
	{
		PutLL(_target, hash_1);
		PutLL(_target, pow_base_1);
		PutLL(_target, hash_2);
		PutLL(_target, pow_base_2);
		Send(_target);
	}

	void receive(int _source)
	{
		int source = Receive(_source);
		hash_1 = GetLL(source);
		pow_base_1 = GetLL(source);
		hash_2 = GetLL(source);
		pow_base_2 = GetLL(source);
	}
};



int main()
{
	long long workable = 10000000000;

	int myid = MyNodeId();
	int nodes = NumberOfNodes();

	long long signal_len = SignalLength();
	long long seq_len = SeqLength();

	hash_t signal_hash_1 = 0;
	hash_t signal_hash_2 = 0;

	hash_t total_base_1 = 1; // only instance 0
	hash_t total_base_2 = 1;

	if (signal_len > workable) { // distributed computation
		long long step = signal_len / nodes;
		long long start = step * myid;
		long long end = (myid == nodes - 1 ? signal_len : start + step);
		++start; ++end;

		hash_data part_hash;
		for (long long i = start; i < end; ++i) {
			long long signal_at = SignalAt(i);
			part_hash.hash_1 = hash_f1(part_hash.hash_1, 0, signal_at);
			part_hash.hash_2 = hash_f2(part_hash.hash_2, 0, signal_at);
			part_hash.pow_base_1 *= base_1;
			part_hash.pow_base_2 *= base_2;
		}

		if (myid == 0) {
			hash_data master_hash = part_hash;

			for (int i = 1; i < nodes; ++i) {
				part_hash.receive(i);

				master_hash.hash_1 = master_hash.hash_1 * part_hash.pow_base_1 + part_hash.hash_1;
				master_hash.hash_2 = master_hash.hash_2 * part_hash.pow_base_2 + part_hash.hash_2;

				master_hash.pow_base_1 *= part_hash.pow_base_1;
				master_hash.pow_base_2 *= part_hash.pow_base_2;
			}
			signal_hash_1 = master_hash.hash_1;
			signal_hash_2 = master_hash.hash_2;

			for (int i = 1; i < nodes; ++i) {
				PutLL(i, signal_hash_1);
				PutLL(i, signal_hash_1);
				Send(i);
			}
		} else {
			part_hash.send(0);

			int source = Receive(0);
			signal_hash_1 = GetLL(source);
			signal_hash_2 = GetLL(source);
		}
	} else { // single computation
		if (myid == 0) {
			for (long long i = 1; i <= signal_len; ++i) {
				long long signal_at = SignalAt(i);
				signal_hash_1 = hash_f1(signal_hash_1, 0, static_cast<hash_t>(signal_at));
				signal_hash_2 = hash_f2(signal_hash_2, 0, static_cast<hash_t>(signal_at));
			}
			for (int i = 1; i < nodes; ++i) {
				PutLL(i, signal_hash_1);
				PutLL(i, signal_hash_2);
				Send(i);
			}
		} else {
			int source = Receive(0);
			signal_hash_1 = GetLL(source);
			signal_hash_2 = GetLL(source);
		}
	}

	// signal_hashes are ready
	// split work and calc maches in distributed manner

	long long diff = seq_len - signal_len;
	if (diff > workable && nodes != 1) { // distributed hashing of parts
		if (myid == nodes - 1) {
			std::vector<hash_data> hashes;
			std::vector<long long> begins(nodes + 1);
			std::vector<long long> lines;
			lines.reserve(nodes * 3);

			long long step = diff / (nodes + 1); // if bugs then diff switch to seq_len
			for (int i = 0; i < nodes + 1; ++i) {
				lines.push_back(i * step + 1);
				begins[i] = i * step + 1;
				if (i * step + signal_len + 1 <= seq_len) {
					lines.push_back(i * step + signal_len + 1);
				}
			}
			lines.push_back(seq_len + 1);
			std::sort(lines.begin(), lines.end());
			lines.resize(std::distance(lines.begin(), std::unique(lines.begin(), lines.end())));

			int idx = 0, count = 0;
			while (idx + 1 < lines.size()) {
				for (int i = 0; i < nodes - 1 && idx + 1 < lines.size(); ++i) {
					PutLL(i, lines[idx]);
					PutLL(i, lines[idx + 1]);
					Send(i);
					++idx;
				}
			}
			for (int i = 0; i < nodes - 1; ++i) {
				PutLL(i, -1);
				PutLL(i, -1);
				Send(i);
			}
			hashes.resize(idx);
			while (idx) {
				for (int i = 0; i < nodes - 1 && idx; ++i) {
					hashes[count].receive(i);
					++count;
					--idx;
				}
			}

			// setup master hashes and divide work equally for each node
			long long beg_idx = 0;
			long long end_idx = 0;
			long long instance = 0;
			hash_data master_hash;
			for (int i = 0; i < hashes.size() && instance < nodes;) {
				if (lines[end_idx] - begins[beg_idx] == signal_len) {
					if (instance == myid) {
						break;
					}
					master_hash.send(instance++);
					master_hash = hash_data();
					end_idx = 0;
					while (lines[end_idx] < begins[beg_idx]) {
						++end_idx;
					}
					i = end_idx;
					++beg_idx;
				} else {
					master_hash.hash_1 = master_hash.hash_1 * hashes[i].pow_base_1 + hashes[i].hash_1;
					master_hash.hash_2 = master_hash.hash_2 * hashes[i].pow_base_2 + hashes[i].hash_2;
					master_hash.pow_base_1 *= hashes[i].pow_base_1;
					master_hash.pow_base_2 *= hashes[i].pow_base_2;
					++end_idx;
					++i;
				}
			}

			// master hash is ready
			//long long step = diff / (nodes + 1);
			long long start = step * myid + 1;
			long long end = seq_len + 1;

			std::mt19937 generator;
			std::uniform_int_distribution<long long> distribution(1, signal_len - 1);

			const int test_count = 5;

			long long result = 0;
			for (long long i = start; i < end; ++i) {
				if (master_hash.hash_1 == signal_hash_1 &&
					master_hash.hash_2 == signal_hash_2) {
					long long correct = 0;
					for (int j = 0; j < test_count; ++j) {
						long long rand_test = distribution(generator);
						if (SeqAt(rand_test + i - 1) == SignalAt(rand_test)) {
							++correct;
						}
					}
					if (correct == test_count) {
						++result;
					}
				}
				long long seq_at_i = SeqAt(i);
				long long seq_at_sl = SeqAt(i + signal_len);
				master_hash.hash_1 = base_1 * master_hash.hash_1 + seq_at_sl - master_hash.pow_base_1 * seq_at_i;
				master_hash.hash_2 = base_2 * master_hash.hash_2 + seq_at_sl - master_hash.pow_base_2 * seq_at_i;
			}

			PutLL(0, result);
			Send(0);

		} else {
			while (true) {
				int source = Receive(nodes - 1);
				long long start = GetLL(source);
				long long end = GetLL(source);

				if (start == -1 && end == -1) {
					break;
				}

				hash_data result;
				for (long long i = start; i < end; ++i) {
					long long seq_at = SeqAt(i);
					result.hash_1 = hash_f1(result.hash_1, 0, seq_at);
					result.hash_2 = hash_f2(result.hash_2, 0, seq_at);

					result.pow_base_1 *= base_1;
					result.pow_base_2 *= base_2;
				}

				result.send(nodes - 1);
			}

			// receive master hash and search for solutions
			hash_data master_hash;
			master_hash.receive(nodes - 1);

			long long step = diff / (nodes + 1);
			long long start = step * myid + 1;
			long long end = step * (myid + 1) + 1;

			std::mt19937 generator;
			std::uniform_int_distribution<long long> distribution(1, signal_len - 1);

			const int test_count = 5;

			long long result = 0;
			for (long long i = start; i < end; ++i) {
				if (master_hash.hash_1 == signal_hash_1 &&
					master_hash.hash_2 == signal_hash_2) {
					long long correct = 0;
					for (int j = 0; j < test_count; ++j) {
						long long rand_test = distribution(generator);
						if (SeqAt(rand_test + i - 1) == SignalAt(rand_test)) {
							++correct;
						}
					}
					if (correct == test_count) {
						++result;
					}
				}
				long long seq_at_i = SeqAt(i);
				long long seq_at_sl = SeqAt(i + signal_len);
				// possible bug when master_hash.pow_base_1 != total_base_1 and so on (...)
				master_hash.hash_1 = base_1 * master_hash.hash_1 + seq_at_sl - master_hash.pow_base_1 * seq_at_i;
				master_hash.hash_2 = base_2 * master_hash.hash_2 + seq_at_sl - master_hash.pow_base_2 * seq_at_i;
			}

			if (myid == 0) {
				for (int i = 1; i < nodes; ++i) {
					int source = Receive(i);
					result += GetLL(source);
				}
				std::cout << result << std::endl;
				// FINITO
			} else {
				PutLL(0, result);
				Send(0);
			}
		}

	} else {
		if (seq_len > workable) { // distributed hashing of whole subsequence of sequence with length of signal
			long long step = signal_len / nodes;
			long long start = step * myid;
			long long end = (myid == nodes - 1 ? signal_len : start + step);
			++start; ++end;

			hash_data part_hash;
			for (long long i = start; i < end; ++i) {
				long long seq_at = SeqAt(i);
				part_hash.hash_1 = hash_f1(part_hash.hash_1, 0, static_cast<hash_t>(seq_at));
				part_hash.hash_2 = hash_f2(part_hash.hash_2, 0, static_cast<hash_t>(seq_at));
				part_hash.pow_base_1 *= base_1;
				part_hash.pow_base_2 *= base_2;
			}
			if (myid == 0) {
				hash_data master_hash = part_hash;

				for (int i = 1; i < nodes; ++i) {
					part_hash.receive(i);

					master_hash.hash_1 = master_hash.hash_1 * part_hash.pow_base_1 + part_hash.hash_1;
					master_hash.hash_2 = master_hash.hash_2 * part_hash.pow_base_2 + part_hash.hash_2;

					master_hash.pow_base_1 *= part_hash.pow_base_1;
					master_hash.pow_base_2 *= part_hash.pow_base_2;
				}

				std::mt19937 generator;
				std::uniform_int_distribution<long long> distribution(1, signal_len - 1);

				const int test_count = 5;

				long long result = 0;
				for (long long i = start; i < end; ++i) {
					if (master_hash.hash_1 == signal_hash_1 &&
						master_hash.hash_2 == signal_hash_2) {
						long long correct = 0;
						for (int j = 0; j < test_count; ++j) {
							long long rand_test = distribution(generator);
							if (SeqAt(rand_test + i - 1) == SignalAt(rand_test)) {
								++correct;
							}
						}
						if (correct == test_count) {
							++result;
						}
					}
					long long seq_at_i = SeqAt(i);
					long long seq_at_sl = SeqAt(i + signal_len);
					// possible bug when master_hash.pow_base_1 != total_base_1 and so on (...)
					master_hash.hash_1 = base_1 * master_hash.hash_1 + seq_at_sl - master_hash.pow_base_1 * seq_at_i;
					master_hash.hash_2 = base_2 * master_hash.hash_2 + seq_at_sl - master_hash.pow_base_2 * seq_at_i;
				}

				std::cout << result << std::endl;

			} else {
				part_hash.send(0);
			}

		} else { // single computation of pattern matching
				 // need to compute hash of seq of length S
			if (myid == 0) {
				long long start = 1;
				long long end = seq_len + 1;

				hash_data master_hash;
				for (long long i = start; i < start + signal_len; ++i) {
					long long seq_at = SeqAt(i);
					master_hash.hash_1 = hash_f1(master_hash.hash_1, 0, seq_at);
					master_hash.hash_2 = hash_f2(master_hash.hash_2, 0, seq_at);

					master_hash.pow_base_1 *= base_1;
					master_hash.pow_base_2 *= base_2;
				}

				std::mt19937 generator;
				std::uniform_int_distribution<long long> distribution(1, signal_len - 1);

				const int test_count = 5;

				long long result = 0;
				for (long long i = start; i < end - signal_len; ++i) {
					if (master_hash.hash_1 == signal_hash_1 &&
						master_hash.hash_2 == signal_hash_2) {
						long long correct = 0;
						for (int j = 0; j < test_count; ++j) {
							long long rand_test = distribution(generator);
							if (SeqAt(rand_test + i - 1) == SignalAt(rand_test)) {
								++correct;
							}
						}
						if (correct == test_count) {
							++result;
						}
					}
					long long seq_at_i = SeqAt(i);
					long long seq_at_sl = SeqAt(i + signal_len);
					// possible bug when master_hash.pow_base_1 != total_base_1 and so on (...)
					master_hash.hash_1 = base_1 * master_hash.hash_1 + seq_at_sl - master_hash.pow_base_1 * seq_at_i;
					master_hash.hash_2 = base_2 * master_hash.hash_2 + seq_at_sl - master_hash.pow_base_2 * seq_at_i;
				}

				std::cout << result << std::endl;
			}
		}
	}

	return 0;
}