#include <iostream> #include <vector> #include <queue> #include <algorithm> #include <string> #include "message.h" #include "poszukiwania.h" using namespace std; int main() { ios_base::sync_with_stdio(0); if(MyNodeId() != 0) return 0; int sig_l = SignalLength(), seq_l = SeqLength(); vector < int > signal(sig_l + 1); for(int i = 0; i < sig_l; i++) signal[i] = SignalAt(i + 1); signal.back() = -1; vector < int > P(signal.size()); int n = sig_l + seq_l + 1, t = 0; P[0] = 0; P[1] = 0; int cnt = 0; for(int i = 1; i < n; i++) { int a = (i > sig_l + 1 ? SeqAt(i - sig_l - 1) : signal[i]); while (t > 0 && signal[t] != a) t = P[t-1]; if (signal[t] == a) t++; if(i < P.size()) P[i] = t; else if(t == sig_l) cnt++; } cout << cnt; 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 | #include <iostream> #include <vector> #include <queue> #include <algorithm> #include <string> #include "message.h" #include "poszukiwania.h" using namespace std; int main() { ios_base::sync_with_stdio(0); if(MyNodeId() != 0) return 0; int sig_l = SignalLength(), seq_l = SeqLength(); vector < int > signal(sig_l + 1); for(int i = 0; i < sig_l; i++) signal[i] = SignalAt(i + 1); signal.back() = -1; vector < int > P(signal.size()); int n = sig_l + seq_l + 1, t = 0; P[0] = 0; P[1] = 0; int cnt = 0; for(int i = 1; i < n; i++) { int a = (i > sig_l + 1 ? SeqAt(i - sig_l - 1) : signal[i]); while (t > 0 && signal[t] != a) t = P[t-1]; if (signal[t] == a) t++; if(i < P.size()) P[i] = t; else if(t == sig_l) cnt++; } cout << cnt; return 0; } |