#include <iostream> #include <vector> #include "message.h" #include "poszukiwania.h" using namespace std; typedef long long ll; typedef vector<ll> vll; vll S, P; ll KMP() { if (P.size() > S.size()) return 0; vll T(P.size() + 1, -1); vll matches; ll x = 0; for(ll i = 1; i <= P.size(); ++i) { ll pos = T[i - 1]; while(pos != -1 && P[pos] != P[i - 1]) pos = T[pos]; T[i] = pos + 1; } ll sp = 0; ll kp = 0; while(sp < S.size()) { while(kp != -1 && (kp == P.size() || P[kp] != S[sp])) kp = T[kp]; ++kp; ++sp; if(kp == P.size()){ matches.push_back(sp - P.size()); ++x; } } return x; } void readSequence(ll from, ll to){ ll len = to - from; S = vll(len); for (ll i = 0; i < len; ++i) { S[i] = SeqAt(from); ++from; } ll sigLen = SignalLength(); P = vll(sigLen); for (ll i = 0; i < sigLen; ++i) P[i] = SeqAt(i); } int main() { int node = MyNodeId(); int N = NumberOfNodes(); ll SL = SeqLength(); ll PL = SignalLength(); ll partL = (ll)SL/(N -1); if(partL >= PL) { if (node != 0){ if (node < (N - 1)) readSequence(partL*(node -1),partL*node + PL); else readSequence(partL*(node -1),SL); ll r = KMP(); PutLL(0, r); Send(0); } else { ll sumP = 0; int source; int recieved = 0; while (recieved < N-1){ source = Receive(-1); sumP+= GetLL(source); recieved++; } cout<<sumP<<endl; } } else if (node == 0){ readSequence(0, SL); cout << KMP()<<endl; } }
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 | #include <iostream> #include <vector> #include "message.h" #include "poszukiwania.h" using namespace std; typedef long long ll; typedef vector<ll> vll; vll S, P; ll KMP() { if (P.size() > S.size()) return 0; vll T(P.size() + 1, -1); vll matches; ll x = 0; for(ll i = 1; i <= P.size(); ++i) { ll pos = T[i - 1]; while(pos != -1 && P[pos] != P[i - 1]) pos = T[pos]; T[i] = pos + 1; } ll sp = 0; ll kp = 0; while(sp < S.size()) { while(kp != -1 && (kp == P.size() || P[kp] != S[sp])) kp = T[kp]; ++kp; ++sp; if(kp == P.size()){ matches.push_back(sp - P.size()); ++x; } } return x; } void readSequence(ll from, ll to){ ll len = to - from; S = vll(len); for (ll i = 0; i < len; ++i) { S[i] = SeqAt(from); ++from; } ll sigLen = SignalLength(); P = vll(sigLen); for (ll i = 0; i < sigLen; ++i) P[i] = SeqAt(i); } int main() { int node = MyNodeId(); int N = NumberOfNodes(); ll SL = SeqLength(); ll PL = SignalLength(); ll partL = (ll)SL/(N -1); if(partL >= PL) { if (node != 0){ if (node < (N - 1)) readSequence(partL*(node -1),partL*node + PL); else readSequence(partL*(node -1),SL); ll r = KMP(); PutLL(0, r); Send(0); } else { ll sumP = 0; int source; int recieved = 0; while (recieved < N-1){ source = Receive(-1); sumP+= GetLL(source); recieved++; } cout<<sumP<<endl; } } else if (node == 0){ readSequence(0, SL); cout << KMP()<<endl; } } |