#include <vector> #include <cstdio> #include "message.h" #include "poszukiwania.h" using namespace std; int main() { if(MyNodeId() == 0) { unsigned int s_len = SignalLength(); unsigned int m_len = SeqLength(); vector<unsigned int> ans; vector<unsigned int> T(s_len+1, -1); for(int i = 1; i <= s_len; i++) { unsigned int pos = T[i - 1]; while(pos != -1 && SignalAt(pos+1) != SignalAt(i)) pos = T[pos]; T[i] = pos + 1; } unsigned int sp = 0; unsigned int kp = 0; while(sp < m_len) { while(kp != -1 && (kp == s_len || SignalAt(kp+1) != SeqAt(sp+1))) kp = T[kp]; kp++; sp++; if(kp == s_len) ans.push_back(sp - s_len); } printf("%lld\n", ans.size()); } 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 | #include <vector> #include <cstdio> #include "message.h" #include "poszukiwania.h" using namespace std; int main() { if(MyNodeId() == 0) { unsigned int s_len = SignalLength(); unsigned int m_len = SeqLength(); vector<unsigned int> ans; vector<unsigned int> T(s_len+1, -1); for(int i = 1; i <= s_len; i++) { unsigned int pos = T[i - 1]; while(pos != -1 && SignalAt(pos+1) != SignalAt(i)) pos = T[pos]; T[i] = pos + 1; } unsigned int sp = 0; unsigned int kp = 0; while(sp < m_len) { while(kp != -1 && (kp == s_len || SignalAt(kp+1) != SeqAt(sp+1))) kp = T[kp]; kp++; sp++; if(kp == s_len) ans.push_back(sp - s_len); } printf("%lld\n", ans.size()); } return 0; } |