#include <algorithm> #include <vector> #include <iostream> #include "poszukiwania.h" #include "message.h" void fillKMPTable(std::vector<int> &KMPTable) { long long signalLength = SignalLength(); KMPTable.resize(size_t(signalLength + 1)); KMPTable[0] = 0, KMPTable[1] = 1; long long signalFrontIndex = 1; for (long long signalBackIndex = 2; signalBackIndex < signalLength + 1;) { if (SignalAt(signalFrontIndex) == SignalAt(signalBackIndex)) { KMPTable[size_t(signalBackIndex)] = int(++signalFrontIndex); ++signalBackIndex; } else if (signalFrontIndex > 1) { signalFrontIndex = KMPTable[size_t(signalFrontIndex - 1)]; } else { KMPTable[size_t(signalBackIndex)] = 1; signalFrontIndex = 1; ++signalBackIndex; } } } long long findMatchesKMP(long long from, long long to) { if (from >= to) { return 0; } std::vector<int> KMPTable; fillKMPTable(KMPTable); long long matchesFound = 0; for (long long wordIndex = from, patternIndex = 1; wordIndex - patternIndex + 1 < to;) { if (SeqAt(wordIndex) == SignalAt(patternIndex)) { ++wordIndex, ++patternIndex; } else if (patternIndex > 1) { patternIndex = KMPTable[size_t(patternIndex)]; } else { patternIndex = 1, ++wordIndex; } if (patternIndex == SignalLength() + 1) { ++matchesFound; patternIndex = KMPTable[size_t(patternIndex - 1)]; } } return matchesFound; } // heuristic enum HashType { SUM_HASH = 0, DEC_HASH = 1, INC_HASH = 2, }; void initHeuristics(long long from, long long (&patternHashes)[3], long long(&wordHashes)[3]) { patternHashes[0] = patternHashes[1] = patternHashes[2] = wordHashes[0] = wordHashes[1] = wordHashes[2] = 0; long long signalLen = SignalLength(); long long currentSignal = 0; long long currentSeq = 0; for (int i = 1; i <= signalLen; ++i) { currentSignal = SignalAt(i); currentSeq = SeqAt(from + i - 1); patternHashes[SUM_HASH] += currentSignal; wordHashes[SUM_HASH] += currentSeq; patternHashes[DEC_HASH] += patternHashes[SUM_HASH]; wordHashes[DEC_HASH] += wordHashes[SUM_HASH]; patternHashes[INC_HASH] += i * currentSignal; wordHashes[INC_HASH] += i * currentSeq; } } void updateHashes(long long dropElem, long long(&wordHashes)[3]) { long long signalLength = SignalLength(); long long dropSeq = SeqAt(dropElem); long long addSeq = SeqAt(dropElem + signalLength); wordHashes[INC_HASH] -= wordHashes[SUM_HASH]; wordHashes[INC_HASH] += signalLength * addSeq; wordHashes[SUM_HASH] -= dropSeq; wordHashes[SUM_HASH] += addSeq; wordHashes[DEC_HASH] += wordHashes[SUM_HASH]; wordHashes[DEC_HASH] -= signalLength * dropSeq; } bool hashesAreEqual(long long(&patternHashes)[3], long long(&wordHashes)[3]) { return patternHashes[0] == wordHashes[0] && patternHashes[1] == wordHashes[1] && patternHashes[2] == wordHashes[2]; } long long findMatchesHeuristic(long long from, long long to) { if (from >= to) { return 0; } long long patternHashes[3], wordHashes[3]; initHeuristics(from, patternHashes, wordHashes); long long matchesFound = 0; for (long long i = from; i < to - 1; ++i) { if (hashesAreEqual(patternHashes, wordHashes)) { ++matchesFound; } updateHashes(i, wordHashes); } if (hashesAreEqual(patternHashes, wordHashes)) { ++matchesFound; } return matchesFound; } int main() { long long nodeId = MyNodeId(); int numberOfNodes = NumberOfNodes(); long long potentialMatchPositions = SeqLength() - SignalLength() + 1; long long nodeCount = (potentialMatchPositions + numberOfNodes - 1) / numberOfNodes; long long nodeStart = nodeId * nodeCount + 1; long long nodeEnd = std::min(nodeStart + nodeCount, potentialMatchPositions + 1); long long matchesFound = 0; if (SignalLength() <= 2 * 10000000) { matchesFound = findMatchesKMP(nodeStart, nodeEnd); } else { matchesFound = findMatchesHeuristic(nodeStart, nodeEnd); } if (nodeId > 0) { PutLL(0, matchesFound); Send(0); } else { for (int i = 0; i < numberOfNodes - 1; ++i) { int inst = Receive(-1); matchesFound += GetLL(inst); } std::cout << matchesFound; } }
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 122 123 124 125 126 127 128 129 130 131 132 133 134 135 | #include <algorithm> #include <vector> #include <iostream> #include "poszukiwania.h" #include "message.h" void fillKMPTable(std::vector<int> &KMPTable) { long long signalLength = SignalLength(); KMPTable.resize(size_t(signalLength + 1)); KMPTable[0] = 0, KMPTable[1] = 1; long long signalFrontIndex = 1; for (long long signalBackIndex = 2; signalBackIndex < signalLength + 1;) { if (SignalAt(signalFrontIndex) == SignalAt(signalBackIndex)) { KMPTable[size_t(signalBackIndex)] = int(++signalFrontIndex); ++signalBackIndex; } else if (signalFrontIndex > 1) { signalFrontIndex = KMPTable[size_t(signalFrontIndex - 1)]; } else { KMPTable[size_t(signalBackIndex)] = 1; signalFrontIndex = 1; ++signalBackIndex; } } } long long findMatchesKMP(long long from, long long to) { if (from >= to) { return 0; } std::vector<int> KMPTable; fillKMPTable(KMPTable); long long matchesFound = 0; for (long long wordIndex = from, patternIndex = 1; wordIndex - patternIndex + 1 < to;) { if (SeqAt(wordIndex) == SignalAt(patternIndex)) { ++wordIndex, ++patternIndex; } else if (patternIndex > 1) { patternIndex = KMPTable[size_t(patternIndex)]; } else { patternIndex = 1, ++wordIndex; } if (patternIndex == SignalLength() + 1) { ++matchesFound; patternIndex = KMPTable[size_t(patternIndex - 1)]; } } return matchesFound; } // heuristic enum HashType { SUM_HASH = 0, DEC_HASH = 1, INC_HASH = 2, }; void initHeuristics(long long from, long long (&patternHashes)[3], long long(&wordHashes)[3]) { patternHashes[0] = patternHashes[1] = patternHashes[2] = wordHashes[0] = wordHashes[1] = wordHashes[2] = 0; long long signalLen = SignalLength(); long long currentSignal = 0; long long currentSeq = 0; for (int i = 1; i <= signalLen; ++i) { currentSignal = SignalAt(i); currentSeq = SeqAt(from + i - 1); patternHashes[SUM_HASH] += currentSignal; wordHashes[SUM_HASH] += currentSeq; patternHashes[DEC_HASH] += patternHashes[SUM_HASH]; wordHashes[DEC_HASH] += wordHashes[SUM_HASH]; patternHashes[INC_HASH] += i * currentSignal; wordHashes[INC_HASH] += i * currentSeq; } } void updateHashes(long long dropElem, long long(&wordHashes)[3]) { long long signalLength = SignalLength(); long long dropSeq = SeqAt(dropElem); long long addSeq = SeqAt(dropElem + signalLength); wordHashes[INC_HASH] -= wordHashes[SUM_HASH]; wordHashes[INC_HASH] += signalLength * addSeq; wordHashes[SUM_HASH] -= dropSeq; wordHashes[SUM_HASH] += addSeq; wordHashes[DEC_HASH] += wordHashes[SUM_HASH]; wordHashes[DEC_HASH] -= signalLength * dropSeq; } bool hashesAreEqual(long long(&patternHashes)[3], long long(&wordHashes)[3]) { return patternHashes[0] == wordHashes[0] && patternHashes[1] == wordHashes[1] && patternHashes[2] == wordHashes[2]; } long long findMatchesHeuristic(long long from, long long to) { if (from >= to) { return 0; } long long patternHashes[3], wordHashes[3]; initHeuristics(from, patternHashes, wordHashes); long long matchesFound = 0; for (long long i = from; i < to - 1; ++i) { if (hashesAreEqual(patternHashes, wordHashes)) { ++matchesFound; } updateHashes(i, wordHashes); } if (hashesAreEqual(patternHashes, wordHashes)) { ++matchesFound; } return matchesFound; } int main() { long long nodeId = MyNodeId(); int numberOfNodes = NumberOfNodes(); long long potentialMatchPositions = SeqLength() - SignalLength() + 1; long long nodeCount = (potentialMatchPositions + numberOfNodes - 1) / numberOfNodes; long long nodeStart = nodeId * nodeCount + 1; long long nodeEnd = std::min(nodeStart + nodeCount, potentialMatchPositions + 1); long long matchesFound = 0; if (SignalLength() <= 2 * 10000000) { matchesFound = findMatchesKMP(nodeStart, nodeEnd); } else { matchesFound = findMatchesHeuristic(nodeStart, nodeEnd); } if (nodeId > 0) { PutLL(0, matchesFound); Send(0); } else { for (int i = 0; i < numberOfNodes - 1; ++i) { int inst = Receive(-1); matchesFound += GetLL(inst); } std::cout << matchesFound; } } |