#include <cstdio> #include <vector> #include "message.h" #include "poszukiwania.h" using namespace std; typedef long long ll; int mId, mCount; ll signalSize, sequenceSize; vector<ll> pxsx, ssignal, sequence; void prefix_suffix() { ll diff = 0; for(ll i = 1; i < signalSize; i++) { while(diff > 0 && ssignal[i] != ssignal[diff]) diff=pxsx[diff - 1]; if(ssignal[i] == ssignal[diff]) pxsx[i] = ++diff; else pxsx[i] = 0; } } int solve(int beg, int end) { int counter = 0, index = 0; for(ll i = beg; i < end; i++){ while(index > 0 && sequence[i] != ssignal[index]) index = pxsx[index - 1]; if(sequence[i] == ssignal[index]) ++index; if(index == signalSize) { ++counter; index = pxsx[index - 1]; } } return counter; } bool brute_check() { for(int i = 0; i < sequenceSize; i++) if(ssignal[i] != sequence[i]) return false; return true; } int min(int a, int b) { return a < b ? a : b; } int max(int a, int b) { return a > b ? a : b; } int main() { mId = MyNodeId(); mCount = NumberOfNodes(); signalSize = SignalLength(); ssignal.resize(signalSize); pxsx.resize(signalSize); sequenceSize = SeqLength(); mCount = min(sequenceSize/signalSize, mCount); if(mId >= mCount) return 0; int yourBeg = (mId == 0) ? 0 : max(sequenceSize/mCount - signalSize+1,0), yourEnd = min((mId+1)*sequenceSize/mCount,sequenceSize); sequence.resize(sequenceSize); for(int i = 0; i < signalSize; i++) ssignal[i] = SignalAt(i); for(int i = yourBeg; i < yourEnd; i++) sequence[i] = SeqAt(i); if(signalSize == sequenceSize) { if(mId == 0) printf(brute_check() ? "1" : "0"); return 0; } prefix_suffix(); // sequenceSize = yourEnd - yourBeg; int result = solve(yourBeg, yourEnd); if(mId != 0) { PutInt(0, result); Send(0); } else { for(int instancja = 1; instancja < mCount; ++instancja) { Receive(instancja); result += GetInt(instancja); } printf("%d", result); } 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 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | #include <cstdio> #include <vector> #include "message.h" #include "poszukiwania.h" using namespace std; typedef long long ll; int mId, mCount; ll signalSize, sequenceSize; vector<ll> pxsx, ssignal, sequence; void prefix_suffix() { ll diff = 0; for(ll i = 1; i < signalSize; i++) { while(diff > 0 && ssignal[i] != ssignal[diff]) diff=pxsx[diff - 1]; if(ssignal[i] == ssignal[diff]) pxsx[i] = ++diff; else pxsx[i] = 0; } } int solve(int beg, int end) { int counter = 0, index = 0; for(ll i = beg; i < end; i++){ while(index > 0 && sequence[i] != ssignal[index]) index = pxsx[index - 1]; if(sequence[i] == ssignal[index]) ++index; if(index == signalSize) { ++counter; index = pxsx[index - 1]; } } return counter; } bool brute_check() { for(int i = 0; i < sequenceSize; i++) if(ssignal[i] != sequence[i]) return false; return true; } int min(int a, int b) { return a < b ? a : b; } int max(int a, int b) { return a > b ? a : b; } int main() { mId = MyNodeId(); mCount = NumberOfNodes(); signalSize = SignalLength(); ssignal.resize(signalSize); pxsx.resize(signalSize); sequenceSize = SeqLength(); mCount = min(sequenceSize/signalSize, mCount); if(mId >= mCount) return 0; int yourBeg = (mId == 0) ? 0 : max(sequenceSize/mCount - signalSize+1,0), yourEnd = min((mId+1)*sequenceSize/mCount,sequenceSize); sequence.resize(sequenceSize); for(int i = 0; i < signalSize; i++) ssignal[i] = SignalAt(i); for(int i = yourBeg; i < yourEnd; i++) sequence[i] = SeqAt(i); if(signalSize == sequenceSize) { if(mId == 0) printf(brute_check() ? "1" : "0"); return 0; } prefix_suffix(); // sequenceSize = yourEnd - yourBeg; int result = solve(yourBeg, yourEnd); if(mId != 0) { PutInt(0, result); Send(0); } else { for(int instancja = 1; instancja < mCount; ++instancja) { Receive(instancja); result += GetInt(instancja); } printf("%d", result); } return 0; } |