#include <cstdlib> #include <algorithm> #include "message.h" #include "poszukiwania.h" using namespace std; typedef long long ll; int id, non; int signalLen, seqLen; int myFirstP, myLastP; int mySeqEnd; int myCount; int *P; void GetMyPart(); int KmpCount(); void CommunicateAndPrint(); int main() { GetMyPart(); if(myFirstP <= myLastP) myCount = KmpCount(); CommunicateAndPrint(); delete [] P; return 0; } void GetMyPart() { id = MyNodeId(); non = NumberOfNodes(); signalLen = SignalLength(); seqLen = SeqLength(); auto maxP = seqLen - signalLen; auto pCount = maxP + 1; auto pPerNode = pCount/non + (pCount%non ? 1 : 0); myFirstP = id * pPerNode; myLastP = min(myFirstP + pPerNode - 1, maxP); mySeqEnd = myLastP + signalLen; P = new int[signalLen+1]; } void KmpSignal(int&, int); void KmpSeq(int&, int); int KmpCount() { int counter = 0; P[1] = 0; int k = 0,q; for(q = 1; q < signalLen; ++q) { KmpSignal(k, q); P[q+1] = k; } for(q = myFirstP,k = 0; q < mySeqEnd; ++q) { KmpSeq(k, q); if(k == signalLen) { ++counter; k = P[k]; } } return counter; } inline void KmpSignal(int &k, int q) { int siqAtQ = SignalAt(q+1); int sigAtK = SignalAt(k+1); while(k > 0 && sigAtK != siqAtQ) { k = P[k]; sigAtK = SignalAt(k+1); } if(sigAtK == siqAtQ) k++; } inline void KmpSeq(int &k, int q) { int seqAtQ = SeqAt(q+1); int sigAtK = SignalAt(k+1); while(k > 0 && (sigAtK = SignalAt(k+1)) != seqAtQ) { k = P[k]; sigAtK = SignalAt(k+1); } if(sigAtK == seqAtQ) k++; } void CommunicateAndPrint() { if(id == 0) { int allCount = myCount; for(int i = 1; i < non; ++i) { int src = Receive(-1); allCount += GetInt(src); } printf("%d", allCount); } else { PutInt(0, myCount); Send(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 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 | #include <cstdlib> #include <algorithm> #include "message.h" #include "poszukiwania.h" using namespace std; typedef long long ll; int id, non; int signalLen, seqLen; int myFirstP, myLastP; int mySeqEnd; int myCount; int *P; void GetMyPart(); int KmpCount(); void CommunicateAndPrint(); int main() { GetMyPart(); if(myFirstP <= myLastP) myCount = KmpCount(); CommunicateAndPrint(); delete [] P; return 0; } void GetMyPart() { id = MyNodeId(); non = NumberOfNodes(); signalLen = SignalLength(); seqLen = SeqLength(); auto maxP = seqLen - signalLen; auto pCount = maxP + 1; auto pPerNode = pCount/non + (pCount%non ? 1 : 0); myFirstP = id * pPerNode; myLastP = min(myFirstP + pPerNode - 1, maxP); mySeqEnd = myLastP + signalLen; P = new int[signalLen+1]; } void KmpSignal(int&, int); void KmpSeq(int&, int); int KmpCount() { int counter = 0; P[1] = 0; int k = 0,q; for(q = 1; q < signalLen; ++q) { KmpSignal(k, q); P[q+1] = k; } for(q = myFirstP,k = 0; q < mySeqEnd; ++q) { KmpSeq(k, q); if(k == signalLen) { ++counter; k = P[k]; } } return counter; } inline void KmpSignal(int &k, int q) { int siqAtQ = SignalAt(q+1); int sigAtK = SignalAt(k+1); while(k > 0 && sigAtK != siqAtQ) { k = P[k]; sigAtK = SignalAt(k+1); } if(sigAtK == siqAtQ) k++; } inline void KmpSeq(int &k, int q) { int seqAtQ = SeqAt(q+1); int sigAtK = SignalAt(k+1); while(k > 0 && (sigAtK = SignalAt(k+1)) != seqAtQ) { k = P[k]; sigAtK = SignalAt(k+1); } if(sigAtK == seqAtQ) k++; } void CommunicateAndPrint() { if(id == 0) { int allCount = myCount; for(int i = 1; i < non; ++i) { int src = Receive(-1); allCount += GetInt(src); } printf("%d", allCount); } else { PutInt(0, myCount); Send(0); } } |