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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
#include "message.h"
#include "poszukiwania.h"

#include <cstdio>
#include <algorithm>

// #define DEBUG

using namespace std;

typedef long long unsigned LLU_t;

const LLU_t BASE=1074824249LL;
const LLU_t MAX_INSTANCES=105;

//Compute at startup 'constants':
int INSTANCES;
int MY_ID;

const auto& getS = SignalAt;
const auto& getM = SeqAt;
LLU_t S_LEN;
LLU_t M_LEN;
LLU_t S_INTERVAL_LEN;
LLU_t M_INTERVAL_LEN;

LLU_t S_HASH=0;
LLU_t M_HASH[MAX_INSTANCES]={};

//Getting interval of any instance:
LLU_t startS(int instanceId) {
	return instanceId*S_INTERVAL_LEN+1;
}
LLU_t endS(int instanceId) {
	return (instanceId == INSTANCES-1 ? S_LEN : (instanceId+1)*S_INTERVAL_LEN);
}
LLU_t startM(int instanceId) {
	return instanceId*M_INTERVAL_LEN+1;
}
LLU_t endM(int instanceId) {
	return (instanceId == INSTANCES-1 ? M_LEN : (instanceId+1)*M_INTERVAL_LEN);
}

//Fast power:
LLU_t power(LLU_t m, const LLU_t p) {
	LLU_t curPow=1;
	LLU_t res=1;
	
	while (curPow <= p) {
		if ((curPow & p) != 0)
			res = res * m;
		m = m * m;
		curPow <<= 1;
	}
	
	return res;
}

//First phase:

LLU_t mySPart = 0;
LLU_t myMPart = 0;

void computeSPart() {
	LLU_t start = startS(MY_ID);
	LLU_t end = endS(MY_ID);
	LLU_t res = 0;
	
	for (LLU_t i=start; i<=end; ++i) {
		res = res * BASE + getS(i);
	}
	
	mySPart = res;
}


void computeMPart() {
	LLU_t start = startM(MY_ID);
	LLU_t end = endM(MY_ID);
	LLU_t res = 0;
	
	for (LLU_t i=start; i<=end; ++i) {
		res = res * BASE + getM(i);
	}
	
	myMPart = res;
}

void sendSM() {
	for (int id=0; id<INSTANCES; ++id) {
		PutLL(id, mySPart);
		PutLL(id, myMPart);
		Send(id);
	}
}

void gatherSM() {
	S_HASH=0;
	LLU_t lastEnd=0, curEnd;
	
	for (int id=0; id<INSTANCES; ++id) {
		curEnd = endS(id);
		
		Receive(id);
		S_HASH = S_HASH * power(BASE, curEnd-lastEnd) + GetLL(id);
		M_HASH[id] = GetLL(id);
		
		lastEnd = curEnd;
	}
}


LLU_t getMHash(LLU_t from, LLU_t to) {
	LLU_t res=0;
	int startId, endId;
	
	for (startId=0; startId<INSTANCES; ++startId) {
		if (startM(startId) <= from && from <= endM(startId))
			break;
	}
	
	for (endId=0; endId<INSTANCES; ++endId) {
		if (startM(endId) <= from && from <= endM(endId))
			break;
	}
	
	//Whole in one interval:
	if (startId == endId) {
		for (LLU_t i=from; i<=to; ++i)
			res = res * BASE + getM(i);
		return res;
	}
	
	//In multiple intervals:
	LLU_t lastEnd = endM(startId), curEnd;
	
	for (LLU_t i=from; i<=lastEnd; ++i)
		res = res * BASE + getM(i);
	
	for (int id=startId+1; id<endId; ++id) {
		curEnd = endM(id);
		
		res = res * power(BASE, curEnd-lastEnd) + M_HASH[id];
		
		lastEnd = curEnd;
	}
	
	for (LLU_t i=lastEnd+1; i<=to; ++i)
		res = res * BASE + getM(i);
	
	return res;
}

void doMatching() {
	LLU_t curEnd = max(startM(MY_ID), S_LEN);
	LLU_t curStart = curEnd - (S_LEN-1);
	LLU_t curHash = getMHash(curStart, curEnd);
	LLU_t shift = power(BASE, curEnd-curStart);
	LLU_t loopLimit = endM(MY_ID);
	LLU_t matches=0;
	
	while (curEnd <= loopLimit) {
		if (curHash == S_HASH)
			++matches;
		
		if (curEnd>=M_LEN)
			break;
		
		#ifdef DEBUG
			fprintf(stderr, "Checking curStart=%llu  ;  curEnd=%llu\n", curStart, curEnd);
		#endif
		
		curHash -= getM(curStart) * shift;
		curHash = curHash * BASE + getM(curEnd+1);
		
		++curEnd;
		++curStart;
	}
	
	//Sending answer to 0th instance
	PutLL(0, matches);
	Send(0);
}


void gatherAnswers() {
	LLU_t res=0;
	
	for (int id=0; id<INSTANCES; ++id) {
		Receive(id);
		res += GetLL(id);
	}
	
	printf("%llu\n", res);
}


int main() {
	//Setting 'constants':
	INSTANCES = NumberOfNodes();
	MY_ID = MyNodeId();
	S_LEN = SignalLength();
	M_LEN = SeqLength();
	S_INTERVAL_LEN = S_LEN/INSTANCES;
	M_INTERVAL_LEN = M_LEN/INSTANCES;
	
	//Computing stuff:
	#ifdef DEBUG
		if (MY_ID == 0)
			fprintf(stderr, "S_INTERVAL_LEN = %llu  ;  M_INTERVAL_LEN = %llu\n", S_INTERVAL_LEN, M_INTERVAL_LEN);
		fprintf(stderr, "Instance %d  ->  startM=%llu  endM=%llu\n", MY_ID, startM(MY_ID), endM(MY_ID));
	#endif
	
	computeSPart();
	computeMPart();
	sendSM();
	gatherSM();
	
// 	gatherS();
	
// 	#ifdef DEBUG
// 		fprintf(stderr, "Instance %d  ->  computingMPart...\n", MY_ID);
// 	#endif
	
	
// 	gatherM();
	
	#ifdef DEBUG
		fprintf(stderr, "Instance %d  ->  doMatching...\n", MY_ID);
	#endif
	
	doMatching();
	
	if (MY_ID==0)
		gatherAnswers();
	
	return 0;
}