#include "poszukiwania.h" #include "message.h" #include <cstdio> #include <vector> inline int s(int i, int b, int m) { if(i <= m) return SignalAt(i); else if(i == m+1) return -1; else return SeqAt(i-m+b-1); } int main() { int n = SeqLength(), m = SignalLength(), k = NumberOfNodes(), node = MyNodeId(); int b = node*((n-m+1)/k), e = (node != k-1)?((node+1)*((n-m+1)/k)+m-2):(n-1); if(e > n-1) e = n-1; std::vector<int> p(m+e-b+3); int t = 0, res = 0; p[1] = 0; for(int i = 2; i < m+e-b+3; i++) { while(t > 0 && s(t+1, b, m) != s(i, b, m)) t = p[t]; if(s(t+1, b, m) == s(i, b, m)) t++; p[i] = t; if(i > m+1 && p[i] >= m) res++; } if(node > 0) { PutInt(0, res); Send(0); } else { for(int i = 1; i < k; i++) { Receive(i); res += GetInt(i); } printf("%d\n", res); } 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 | #include "poszukiwania.h" #include "message.h" #include <cstdio> #include <vector> inline int s(int i, int b, int m) { if(i <= m) return SignalAt(i); else if(i == m+1) return -1; else return SeqAt(i-m+b-1); } int main() { int n = SeqLength(), m = SignalLength(), k = NumberOfNodes(), node = MyNodeId(); int b = node*((n-m+1)/k), e = (node != k-1)?((node+1)*((n-m+1)/k)+m-2):(n-1); if(e > n-1) e = n-1; std::vector<int> p(m+e-b+3); int t = 0, res = 0; p[1] = 0; for(int i = 2; i < m+e-b+3; i++) { while(t > 0 && s(t+1, b, m) != s(i, b, m)) t = p[t]; if(s(t+1, b, m) == s(i, b, m)) t++; p[i] = t; if(i > m+1 && p[i] >= m) res++; } if(node > 0) { PutInt(0, res); Send(0); } else { for(int i = 1; i < k; i++) { Receive(i); res += GetInt(i); } printf("%d\n", res); } return 0; } |