#include "poszukiwania.h" #include "message.h" #include <algorithm> #include <iostream> using namespace std; int main() { long long N = SeqLength(); long long M = SignalLength(); //pref-suf long long *PI, i, b; PI = new long long [M + 1]; PI[0] = b = -1; for(i = 1; i <= M; ++i) while((b > -1) && (SignalAt(b) != SignalAt(i - 1))) b = PI[b]; PI[i] = ++b; long long nn = NumberOfNodes(); nn = N / nn + ((N % nn > 0) ? 1 : 0); // +M long long my_start = nn * MyNodeId(); long long my_end = my_start + nn + M; long long pp, how_many = 0; pp = b = 0; for(i = my_start; i <= my_end; ++i) { while((b > -1) && (SignalAt(b) != SeqAt(i))) b = PI[b]; if(++b == M) { while(pp < i - b + 1) pp++; ++how_many; pp++; b = PI[b]; } } if (MyNodeId() > 0) { PutLL(0, how_many); Send(0); } else { for (i = 1; i < NumberOfNodes(); ++i) how_many += GetLL(Receive(i)); cout << how_many << endl; } delete [] PI; return 0; }
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 | #include "poszukiwania.h" #include "message.h" #include <algorithm> #include <iostream> using namespace std; int main() { long long N = SeqLength(); long long M = SignalLength(); //pref-suf long long *PI, i, b; PI = new long long [M + 1]; PI[0] = b = -1; for(i = 1; i <= M; ++i) while((b > -1) && (SignalAt(b) != SignalAt(i - 1))) b = PI[b]; PI[i] = ++b; long long nn = NumberOfNodes(); nn = N / nn + ((N % nn > 0) ? 1 : 0); // +M long long my_start = nn * MyNodeId(); long long my_end = my_start + nn + M; long long pp, how_many = 0; pp = b = 0; for(i = my_start; i <= my_end; ++i) { while((b > -1) && (SignalAt(b) != SeqAt(i))) b = PI[b]; if(++b == M) { while(pp < i - b + 1) pp++; ++how_many; pp++; b = PI[b]; } } if (MyNodeId() > 0) { PutLL(0, how_many); Send(0); } else { for (i = 1; i < NumberOfNodes(); ++i) how_many += GetLL(Receive(i)); cout << how_many << endl; } delete [] PI; return 0; } |