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
#include "poszukiwania.h"
#include "message.h"

#include <algorithm>
#include <iostream>

using namespace std;

const int lInstancji = NumberOfNodes();
const int idInstancji = MyNodeId();

int main() {

  long long M = SeqLength();
  long long S = SignalLength();
  
  	long long poczatek = (long long)(idInstancji * (M-S+1) / lInstancji);
	long long koniec = (long long)((idInstancji+1) * (M-S+1) / lInstancji);
  
	long long i,j,t;
	long long P[S+1];
	
	// obliczenie tablicy P
	P[0]=0; P[1]=0; t=0;
	for (j=2; j<=S; j++)
	{
		while ((t>0)&&(SignalAt(t+1)!=SignalAt(j))) t=P[t];
		if (SignalAt(t+1)==SignalAt(j)) t++;
		P[j]=t;
	}
	 
	// algorytm KMP
	i=poczatek+1; j=0;
	long long ileJestFragmentow = 0;
	while (i<=M-S && i <= koniec)
	{
		j=P[j];
		while((j<S)&&(SignalAt(j+1)==SeqAt(i+j)))
			j++;
		if (j==S)
			ileJestFragmentow++;
			
		i+=max(1LL,j-P[j]);
	}
	PutLL(0, ileJestFragmentow);
	Send(0);
	
	if (idInstancji == 0){
		long long suma = 0;
		for (int i = 0; i<lInstancji; i++){
			Receive(i);
			suma += GetLL(i);
		}
		cout << (suma) << endl;
	}
  return 0;
}