1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <iostream>
#include <cstdlib>
#include <ctime>
#include "poszukiwania.h"
#include "message.h"

long long n;
long long m;
int myId;
int nodes;

long long p = 2107456073LL;
long long b = 1401017LL;
long long bb;

long long pow_mod(long long x, long long y)
{
	long long result = 1;
	while (y > 0)
	{
		if (y & 1) result = (result * x) % p;
		x = (x*x) % p;
		y >>= 1;
	}
	return result;
}

long long Compare(long long pos)
{
	for (long long i=1;i<=m;++i)
		if (SeqAt(pos+i) != SignalAt(i))
			return 0;
	return 1;
}

long long init_hash_sig(long long start, long long end)
{
	long long hash = 0;
	for (long long i=start;i<end;++i)
		hash = (hash*b%p + SignalAt(i)) % p;	
	return hash;
}
long long init_hash_seq(long long start)
{
	long long hash = 0;
	for (long long i=0;i<m;++i)
		hash = (hash*b%p + SeqAt(i+start)) % p;	
	return hash;
}

int main(int argc, char **argv)
{	
	std::ios_base::sync_with_stdio(0);
	
	n = SeqLength();
	m = SignalLength();
	myId = MyNodeId();
	nodes = NumberOfNodes();
	
	bb = pow_mod(b, m-1);
	
	long long positions = n-m+1;
	long long batchSize = (positions+nodes-1) / nodes;
	
	long long start = batchSize * myId;
	long long end = std::min(start+batchSize, positions);
	++start;
	++end;
	
	long long hashSize = (m+nodes-1) / nodes;
	long long hstart = hashSize * myId;
	long long hend = std::min(hstart+hashSize, m);
	++hstart;
	++hend;
	
	
	long long sum = 0;
	long long signal = init_hash_sig(hstart, hend);
	
	
	if (myId == 0)
	{
		//signal = init_hash_sig();
		for (int i=1;i<nodes;++i)
		{
			long long hstart = hashSize * i;
			long long hend = std::min(hstart+hashSize, m);
			long long bb2 = pow_mod(b, hend-hstart);
			Receive(i);
			signal = ( signal*bb2%p + GetLL(i) ) % p;
		}
		for (int i=1;i<nodes;++i)
		{
			PutLL(i, signal);
			Send(i);
		}
	}
	else
	{
		PutLL(0, signal);
		Send(0);
		Receive(0);
		signal = GetLL(0);
	}
	long long seq = init_hash_seq(start);
	
	for (long long i=start; i<end; ++i)
	{
		if (signal == seq)
			++sum;
		
		if (i+1 < end)
		{		
			seq = (seq - bb*SeqAt(i)%p + p) % p;
			seq = (seq*b%p + SeqAt(i+m)) % p;
		}
		//sum += Compare(i);	
	}
	
	if (myId == 0)	
	{
		for (int i=1;i<nodes;++i)
		{
			Receive(i);
			sum += GetInt(i);
		}
		
		std::cout << sum << std::endl;
	}
	else
	{
		PutInt(0, sum);
		Send(0);
	}
	
	return 0;
}