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
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>

#define MOD 787
#define d 257
#include "message.h"
#include "poszukiwania.h"

using ll = long long;

using namespace std;

inline ll getHashSignal(ll len)
{
	ll hash = 0;
	for (ll i = 0; i < len; i++)
	{
		hash = (d*hash + SignalAt(i + 1)) % MOD;
	}

	return hash;
}

inline ll getHashSeq(ll len)
{
	ll hash = 0;
	for (ll i = 0; i < len; i++)
	{
		hash = (d*hash + SeqAt(i + 1)) % MOD;
	}

	return hash;
}

inline ll incrementHash(ll hash, ll remove, ll add, ll h)
{
	h = (d*(hash - SeqAt(remove + 1) * h) + SeqAt(add + 1)) % MOD;
	if (h < 0)
		return h + MOD;
	else return h;
}
ll search(ll serachInLen, ll searchForLen)
{
	ll c = 0;
	ll hashFor = getHashSignal(searchForLen);
	ll hash = getHashSeq(searchForLen);
	ll index = 0;

	ll h = 1;                       // d^(m-1) value
	for (ll i = 0; i < searchForLen - 1; i++)
		h = (d*h) % MOD;

	while (true)
	{
		if (hash == hashFor)
			c++;
		if (index >= serachInLen - searchForLen)
			break;

		hash = incrementHash(hash, index, index + searchForLen, h);
		index++;
	}

	return c;
}

int main()
{
	int myNodeId = MyNodeId();

	int m = SignalLength();
	int n = SeqLength();

	if (myNodeId != 0) return 0;

	cout << search(n, m);
	return 0;
	
}