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
#include "poszukiwania.h"
#include "message.h"
#include <bits/stdc++.h>

using namespace std;

//zrobić dla d = 0 - prawdopodobnie wynik tylko od pierwszego i ostatniego węzła

int main(){
	
	if(MyNodeId() == 0){
		int ile = NumberOfNodes();
		long long wyn = 0;
		//int d;
		//int t[ile];
		for(int i = 1; i < ile; i++){
			int idx = Receive(-1);
			int a = GetLL(idx);
			//cout << "kupa " << idx << endl;
			wyn += a;
		}
		cout << wyn << endl;
	}
	else{
		bool spr = 1;
		int WYN = 0;
		int ile = NumberOfNodes();
		long long n, m;
		n = SeqLength();
		m = SignalLength();
		int d = (n - m + 1 + (ile - 2)) / (ile - 1);
		int myid = MyNodeId();
		int p, k;
		
		if(n - m + 1 < ile - 1){
			//cout << "gowno" << endl;
			//cout << "myid: " << myid << endl;
			p = myid;
			k = p + m - 1;
			if(myid > n - m + 1){
				//cout << "gowno" << endl;
				//goto kupa;
				spr = 0;
			}
		}
		
		else{
			p = (myid - 1) * d + 1;
			k = myid * d + m - 1;
			if(p > n - m + 1){
				spr = 0;
			}
			else if(k > n || (myid * d + 1 > n - m + 1) || myid == ile - 1){
				k = n;
			}
		}
		//cout << p << " - " << k << " " << (spr ? "ok" : "zle") << endl;
		if(spr){
				
			int *tab = new int[m + 1];
			//cout << "tutaj" << endl;
			tab[0] = 0;
			for(int i = 1; i <= m; i++){
				tab[i] = SignalAt(i);
			}
				
			//cout << "tutaj" << endl;
		
			/*vector<int>v;
			v.push_back(0);
			for(int i = p; i <= k; i++){
				v.push_back(SeqAt(i));
				//cout << v[v.size() - 1] << " ";
			}*/
			//cout << v.size() - 1 << endl;
			//KMP
			
			//cout << "tutaj" << endl;
			int *t = new int[m + 1];
			//vector<int>t;
			//t.push_back(0);
			//t.push_back(0);
			t[0] = 0;
			t[1] = 0;
			int q = 0;
			for(int i = 2; i <= m; i++){
				while(q > 0 && tab[q + 1] != tab[i]){
					q = t[q];
				}
				if(tab[q + 1] == tab[i]){
					q++;
				}
				t[i] = q;
				
			}
			
			//cout << "tutaj" << endl;
		
			q = 0;
			for(int i = 1; i <= k - p + 1; i++){
				int a = SeqAt(p + i - 1);
				//cout << a << " ";
				while(q > 0 && tab[q + 1] != a){
					q = t[q];
				}
				if(tab[q + 1] == a){
					q++;
				}
				/*if(myid == 1){
					cout << v[i] << " " << q << " ";
				}*/
				if(q == m){
					WYN++;
					q = t[q];
					//cout << i + p - 1 << endl;
				}
			}
		}
		//kupa:
		//cout << myid << ": " << WYN << endl;
		PutLL(0, WYN);
		Send(0);
		
	}
	return 0;
}