#include "poszukiwania.h" #include "message.h" #include <algorithm> #include <iostream> #include <cstdlib> #include <ctime> using namespace std; const long long B = 5; bool doStringsMatch(long long i, long long S) { for(int x = 1; x <= B; x++) { int r = abs(rand()) % S; if(r == 0) r = 1; if(SeqAt(r + i - 1) != SignalAt(r)) return false; } //for(long long j = 1; j <= S; j++) { // if(SeqAt(i + j - 1) != SignalAt(j)) return false; //} return true; } int main() { long long S = SignalLength(); // j - what we search for long long M = SeqLength(); // i - in what we search M >= S int active_nodes = NumberOfNodes(); long long chunk = M / active_nodes; if(chunk < S) { chunk = S; active_nodes = M / chunk; } long long START = MyNodeId() * chunk + 1; long long END = (MyNodeId() + 1) * chunk + S - 1; if(MyNodeId() == active_nodes - 1) { END = M; } if(MyNodeId() < active_nodes) { srand((unsigned int)time(0)); // ALGO long long target = 0; long long rolling = 0; for(long long j = 1; j <= S; j++) { target += SignalAt(j); rolling += SeqAt(START + j - 1); } long long res = 0; if(target == rolling && doStringsMatch(START, S)) res++; for(long long i = START + S; i <= END; i++) { rolling -= SeqAt(i - S); rolling += SeqAt(i); if(target == rolling && doStringsMatch(i - S + 1, S)) res++; } if (MyNodeId() > 0) { PutLL(0, res); Send(0); } else { for(int i = 1; i < active_nodes; i++) { Receive(i); res += GetLL(i); } cout << res << endl; } } 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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | #include "poszukiwania.h" #include "message.h" #include <algorithm> #include <iostream> #include <cstdlib> #include <ctime> using namespace std; const long long B = 5; bool doStringsMatch(long long i, long long S) { for(int x = 1; x <= B; x++) { int r = abs(rand()) % S; if(r == 0) r = 1; if(SeqAt(r + i - 1) != SignalAt(r)) return false; } //for(long long j = 1; j <= S; j++) { // if(SeqAt(i + j - 1) != SignalAt(j)) return false; //} return true; } int main() { long long S = SignalLength(); // j - what we search for long long M = SeqLength(); // i - in what we search M >= S int active_nodes = NumberOfNodes(); long long chunk = M / active_nodes; if(chunk < S) { chunk = S; active_nodes = M / chunk; } long long START = MyNodeId() * chunk + 1; long long END = (MyNodeId() + 1) * chunk + S - 1; if(MyNodeId() == active_nodes - 1) { END = M; } if(MyNodeId() < active_nodes) { srand((unsigned int)time(0)); // ALGO long long target = 0; long long rolling = 0; for(long long j = 1; j <= S; j++) { target += SignalAt(j); rolling += SeqAt(START + j - 1); } long long res = 0; if(target == rolling && doStringsMatch(START, S)) res++; for(long long i = START + S; i <= END; i++) { rolling -= SeqAt(i - S); rolling += SeqAt(i); if(target == rolling && doStringsMatch(i - S + 1, S)) res++; } if (MyNodeId() > 0) { PutLL(0, res); Send(0); } else { for(int i = 1; i < active_nodes; i++) { Receive(i); res += GetLL(i); } cout << res << endl; } } return 0; } |