#include "poszukiwania.h" #include "message.h" #include <algorithm> #include <iostream> using namespace std; #define LL long long int void KMP(void (*fun)(LL)){ LL signalLen = SignalLength(); // wzo LL seqLen = SeqLength(); // str LL p[signalLen + 1], k = 0, q, m; p[1] = 0; // wyznacz tablicę prefiksową for(q = 1; q != signalLen; q++){ while(k > 0 && SignalAt(k+1) != SignalAt(q+1)) k = p[k]; if(SignalAt(k+1) == SignalAt(q+1)) k++; p[q + 1] = k; } m = q; k = 0; // przeszukujemy... for(q = 0; q != seqLen ; q++){ while(k > 0 && SignalAt(k+1) != SeqAt(q+1)) k = p[k]; if(SignalAt(k+1) == SeqAt(q+1)) k++; if(m == k){ fun(q - m + 1); k = p[k]; } } } // KMP LL occurences = 0; void foundOccurence(LL where){ //cout << "Found at: " << where << endl; occurences++; } int main() { LL N = SeqLength(); LL M = SignalLength(); //for(int i=1; i<=N; i++) if(SeqAt(i) == SignalAt(1)) res++; vector<LL> pattern; pattern.resize(N); vector<LL> signal; signal.resize(M); for(LL i=0; i<N; ++i){ //cout << "Accessing seq " << i << endl; pattern[i] = SeqAt(i+1); } for(LL i=0; i<M; ++i){ //cout << "Accessing sig " << i << endl; signal[i] = SignalAt(i+1); } KMP(foundOccurence); if (MyNodeId() == 0) cout << occurences << 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 | #include "poszukiwania.h" #include "message.h" #include <algorithm> #include <iostream> using namespace std; #define LL long long int void KMP(void (*fun)(LL)){ LL signalLen = SignalLength(); // wzo LL seqLen = SeqLength(); // str LL p[signalLen + 1], k = 0, q, m; p[1] = 0; // wyznacz tablicę prefiksową for(q = 1; q != signalLen; q++){ while(k > 0 && SignalAt(k+1) != SignalAt(q+1)) k = p[k]; if(SignalAt(k+1) == SignalAt(q+1)) k++; p[q + 1] = k; } m = q; k = 0; // przeszukujemy... for(q = 0; q != seqLen ; q++){ while(k > 0 && SignalAt(k+1) != SeqAt(q+1)) k = p[k]; if(SignalAt(k+1) == SeqAt(q+1)) k++; if(m == k){ fun(q - m + 1); k = p[k]; } } } // KMP LL occurences = 0; void foundOccurence(LL where){ //cout << "Found at: " << where << endl; occurences++; } int main() { LL N = SeqLength(); LL M = SignalLength(); //for(int i=1; i<=N; i++) if(SeqAt(i) == SignalAt(1)) res++; vector<LL> pattern; pattern.resize(N); vector<LL> signal; signal.resize(M); for(LL i=0; i<N; ++i){ //cout << "Accessing seq " << i << endl; pattern[i] = SeqAt(i+1); } for(LL i=0; i<M; ++i){ //cout << "Accessing sig " << i << endl; signal[i] = SignalAt(i+1); } KMP(foundOccurence); if (MyNodeId() == 0) cout << occurences << endl; return 0; } |