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
#include <cstdio>
#include <vector>

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

using namespace std;

typedef long long ll;

int mId, mCount;
ll signalSize, sequenceSize;
vector<ll> pxsx, ssignal, sequence;
 
void prefix_suffix() {
	ll diff = 0;
	for(ll i = 1; i < signalSize; i++) {
		while(diff > 0 && ssignal[i] != ssignal[diff]) diff=pxsx[diff - 1];
		if(ssignal[i] == ssignal[diff]) pxsx[i] = ++diff;
		else pxsx[i] = 0;
	}
}
	
int solve(int beg, int end) {
	int counter = 0, index = 0;
	for(ll i = beg; i < end; i++){
		while(index > 0 && sequence[i] != ssignal[index]) index = pxsx[index - 1];
		if(sequence[i] == ssignal[index]) ++index;
		if(index == signalSize) {
			++counter;
			index = pxsx[index - 1];
		}
	}
	return counter;
}

bool brute_check() {
	for(int i = 0; i < sequenceSize; i++)
		if(ssignal[i] != sequence[i])
			return false;
	return true;
}

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int main() {

	mId = MyNodeId();
	mCount = NumberOfNodes();

	signalSize = SignalLength();
	ssignal.resize(signalSize);
	pxsx.resize(signalSize);

	sequenceSize = SeqLength();

	mCount = min(sequenceSize/signalSize, mCount);

	if(mId >= mCount) return 0;

	int yourBeg = (mId == 0) ? 0 : max(sequenceSize/mCount - signalSize+1,0),
		yourEnd = min((mId+1)*sequenceSize/mCount,sequenceSize);

	sequence.resize(sequenceSize);

	for(int i = 0; i < signalSize; i++)
		ssignal[i] = SignalAt(i);

	for(int i = yourBeg; i < yourEnd; i++)
		sequence[i] = SeqAt(i);

	if(signalSize == sequenceSize) {
		if(mId == 0)
			printf(brute_check() ? "1" : "0");
		return 0;
	}

	prefix_suffix();

	// sequenceSize = yourEnd - yourBeg;
	int result = solve(yourBeg, yourEnd);

	if(mId != 0) {
		PutInt(0, result);
		Send(0);
	} else {
		for(int instancja = 1; instancja < mCount; ++instancja) {
			Receive(instancja);
			result += GetInt(instancja);
		}
		printf("%d", result);
	}

	return 0;
}