//Jakub Staroń
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>
#include <functional>

#include "message.h"
#include "poszukiwania.h"

#define DEBUG_MODE

using namespace std;

typedef char int8;
typedef unsigned char uint8;
typedef short int int16;
typedef unsigned short int uint16;
typedef int int32;
typedef unsigned int uint32;
typedef long long int64;
typedef unsigned long long uint64;

typedef std::pair<int32,int32> int32_pair;
typedef std::pair<uint32, uint32> uint32_pair;
typedef std::pair<int64,int64> int64_pair;
typedef std::pair<uint64,uint64> uint64_pair;

typedef std::vector<bool> bit_vector;

#ifdef DEBUG_MODE
#define debug_print(x) cerr << #x << " = " << x << endl
#define print_line cerr << "Line " << __LINE__ << endl
#include <cassert>
#else
#define debug_print(x)
#define print_line
#define assert(x)
#endif

#define rep(i, x) for(int32 i = 0 ; i < (x) ; i++)
#define for_range(i, begin, end) for(auto i = (begin) ; i != (end) ; ++i )
#define all(c) (c).begin(),(c).end()
#define sort_all(x) sort( all(x) )
#define divide(a, b) ( ( (b)%(a) ) == 0 )
#define mp(x, y) make_pair(x,y)
#define pb(x) push_back(x)

#define sig(x) ( (x) == 0 ? 0 : ( (x) < 0 ? -1 : 1 ) )

const double epsilon = 1e-5;

template<class T>
void unique(std::vector<T>& v) {
	sort_all(v);
	v.resize( std::unique(all(v)) - v.begin() );
}

ostream& newline(ostream& str) {
	str.put('\n');
	return str;
}

template<typename T1, typename T2>
istream& operator>>(istream& stream, std::pair<T1, T2>& pair) {
	stream >> pair.first >> pair.second;
	return stream;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& stream, const std::pair<T1, T2>& pair) {
#ifdef DEBUG_MODE
	stream << "(" << pair.first << ", " << pair.second << ")";
#else
	stream << pair.first << ' ' << pair.second;
#endif
	return stream;
}

template<class T>
ostream& operator<<(ostream& str, const vector<T>& v) {
	if(!v.empty())	{
		for(int32 i = 0 ; i + 1 < v.size() ; i++)		
			str << v[i] << ' ';		
		str << v.back();
	}
	return str;
}

typedef uint32_pair hash_type;

const hash_type primes(0xFFFFFFFB, 0xFFFFFFBF);
const hash_type multipler(997, 112);

hash_type operator*(uint32 a, const hash_type& v) {
	uint32 first = ( (uint64)a * (uint64)v.first ) % primes.first;
	uint32 second = ( (uint64)a * (uint64)v.second ) % primes.second;
	return hash_type(first, second);
}

hash_type operator+(const hash_type& a, const hash_type& b) {
	uint32 first = ( (uint64)a.first + (uint64)b.first ) % primes.first;
	uint32 second = ( (uint64)a.second + (uint64)b.second ) % primes.second;
	return hash_type(first, second);
}

hash_type operator-(const hash_type& a, const hash_type& b) {
	uint32 first = ( (uint64)a.first + (uint64)primes.first - (uint64)b.first ) % primes.first;
	uint32 second = ( (uint64)a.second + (uint64)primes.second - (uint64)b.second ) % primes.second;
	return hash_type(first, second);
}

inline void operator+=(hash_type& a, const hash_type& b) {
	a = a + b;
}

inline void operator-=(hash_type& a, const hash_type& b) {
	a = a - b;
}

hash_type operator*(const hash_type& a, const hash_type& b) {
	uint32 first = ( (uint64)a.first * (uint64)b.first ) % primes.first;
	uint32 second = ( (uint64)a.second * (uint64)b.second ) % primes.second;
	return hash_type(first, second);
}

inline void operator*=(hash_type& a, const hash_type& b) {
	a = a * b;
}

hash_type Pow(hash_type a, uint64 n) {
	hash_type result(1, 1);
	while (n > 0) {
		if (!divide(2, n))
			result *= a;

		a = a * a;
		n /= 2;
	}
	return result;
}

void PutHash(int target, const hash_type& hash) {
	PutLL(target, hash.first);
	PutLL(target, hash.second);
}

hash_type GetHash(int source) {
	hash_type result;
	result.first = (uint32)GetLL(source);
	result.second = (uint32)GetLL(source);
	return result;
}

uint64_pair GetRange(uint64 length, uint64 index, uint64 max) {
	uint64 partLength = (length + max - 1) / max;
	uint64 begin = min(index * partLength, length);
	uint64 end = min((index + 1) * partLength, length);

	return uint64_pair(begin, end);
}

const uint32 kSequencePartsMultiplier = 3;

class Application {
public:
	Application() {
		numberOfNodes = (uint32)NumberOfNodes();
		myNodeId = (uint32)MyNodeId();
		signalLength = (uint64)SignalLength();
		sequenceLength = (uint64)SeqLength();
	}

	void Run() {
		HashSignalAndSend();

		if (myNodeId == 0)
			ReceivePartialSignalHashesAndSendSignalHash();
		else
			ReceiveSignalHash();

		sequence_hashes.resize(kSequencePartsMultiplier * numberOfNodes);
		CalculatePartialSequenceHashesAndSend();

		if (myNodeId == 0)
			ReceivePartialSequenceHashesAndSendSequenceHashes();
		else
			ReceiveSequenceHashes();

		number_of_occurrences = 0;

		CalculateNumberOfOccurrences();

		if (myNodeId == 0)
			ReceivePartialNumberOfOccurrences();
		else
			SendPartialNumberOfOccurrences();

		if (myNodeId == 0)
			cout << number_of_occurrences << newline;
	}

	void HashSignalAndSend() {
		uint64_pair range = GetRange(signalLength, myNodeId, numberOfNodes);
		hash_type result = CalculateHash(range.first, range.second, SignalAt);
		PutHash(0, result);
		Send(0);
	}

	void ReceivePartialSignalHashesAndSendSignalHash() {
		rep (i, numberOfNodes) {
			Receive(i);
			signal_hash += GetHash(i);
		}

		for_range (id, 1, numberOfNodes) {
			PutHash(id, signal_hash);
			Send(id);
		}
	}

	void ReceiveSignalHash() {
		Receive(0);
		signal_hash = GetHash(0);
	}

	void CalculatePartialSequenceHashesAndSend() {
		rep (i, kSequencePartsMultiplier) {
			uint64_pair range = GetRange(sequenceLength,
																	 kSequencePartsMultiplier * myNodeId + i,
																	 kSequencePartsMultiplier * numberOfNodes);

			hash_type hash = CalculateHash(range.first, range.second, SeqAt);

			PutHash(0, hash);
		}
		Send(0);
	}

	void ReceivePartialSequenceHashesAndSendSequenceHashes() {
		rep (id, numberOfNodes) {
			Receive(id);
			rep (i, kSequencePartsMultiplier) {
				hash_type hash = GetHash(id);
				sequence_hashes[kSequencePartsMultiplier * id + i] = hash;
			}
		}

		for_range (id, 1, numberOfNodes) {
			for (const hash_type& hash : sequence_hashes)
				PutHash(id, hash);
			Send(id);
		}
	}

	void CalculateNumberOfOccurrences() {
		uint64 numberOfPotentialBegins = sequenceLength - signalLength + 1;
		uint64_pair range = GetRange(numberOfPotentialBegins, myNodeId, numberOfNodes);

		if (range.first == range.second)
			return;

		hash_type hash = CalculateInitialSequenceHash(range.first);

		hash_type front_power = Pow(multipler, range.first);
		hash_type back_power = Pow(multipler, range.first + signalLength);
		for (uint64 i = range.first ; i < range.second ; i++) {
			//cerr << "Hash ciagu na pozycji " << i << " to " << hash << endl;
			//cerr << "Hash sygnalu przesuniety odpowiednio to " << signal_hash << endl;

			if (hash == signal_hash * front_power) {
				//cerr << "Jest match na pozycji " << i << endl;
				number_of_occurrences++;
			}

			hash -= GetSequenceAt(i) * front_power;
			hash += GetSequenceAt(i + signalLength) * back_power;

			front_power *= multipler;
			back_power *= multipler;
		}
	}

	hash_type CalculateInitialSequenceHash(uint64 begin) {
		uint64 end = begin + signalLength;
		hash_type result;

		uint32 index = 0;
		while (begin < end) {
			uint64_pair hash_range = GetRange(sequenceLength, index, sequence_hashes.size());
			if (hash_range.first < begin) {
				index++;
				continue;
			}
			else if (hash_range.first == begin) {
				if (hash_range.second <= end) {
					result += sequence_hashes[index];
					begin = hash_range.second;
				}
				else {
					result += CalculateHash(begin, end, SeqAt);
					begin = end;
				}
			}
			else {
				uint64 new_begin = min(end, hash_range.first);
				result += CalculateHash(begin, new_begin, SeqAt);
				begin = new_begin;
			}
		}

		return result;
	}

	void ReceiveSequenceHashes() {
		Receive(0);
		rep (i, sequence_hashes.size())
			sequence_hashes[i] = GetHash(0);
	}

	void ReceivePartialNumberOfOccurrences() {
		for_range(id, 1, numberOfNodes) {
			Receive(id);
			number_of_occurrences += GetLL(id);
		}
	}

	void SendPartialNumberOfOccurrences() {
		PutLL(0, number_of_occurrences);
		Send(0);
	}

	hash_type CalculateHash(uint64 begin, uint64 end, const std::function<long long(long long)>& SequenceGetter) {
		hash_type result;

		hash_type multipler_pow = Pow(multipler, begin);
		for (uint64 i = begin ; i < end ; i++) {
			uint64 signal = (uint64)SequenceGetter(i + 1);
			result += signal * multipler_pow;
			multipler_pow *= multipler;
		}

		return result;
	}

	uint64 GetSequenceAt(uint64 index) {
		if (index >= sequenceLength)
			return 0;
		else
			return (uint64)SeqAt(index + 1);
	}

	uint32 numberOfNodes;
	uint32 myNodeId;
	uint64 signalLength;
	uint64 sequenceLength;

	hash_type signal_hash;

	vector<hash_type> sequence_hashes;

	uint64 number_of_occurrences;
};


int main() {
	ios::sync_with_stdio(0);
	Application application;
	application.Run();
	return 0;
}