#include "message.h" #include "poszukiwania.h" #include <iostream> using namespace std; void liczK(int s, int *k) { int i=0, j=k[0]=-1; while (i<s) { int xi=SignalAt(i+1); while (j>-1 && xi!=SignalAt(j+1)) j=k[j]; ++i; ++j; if (i<s && SignalAt(i+1)==SignalAt(j+1)) k[i]=k[j]; else k[i]=j; } } int main() { int s=SignalLength(), m=SeqLength(), *k=new int[s+1], ile=m-s+1; int pocz=ile*(long long) MyNodeId()/NumberOfNodes(), kon=ile*(MyNodeId()+1LL)/NumberOfNodes(); int wyn=0; liczK(s, k); int i=0, j=pocz; kon+=s-1; while (j<kon) { int xj=SeqAt(j+1); while (i>-1 && i<s && SignalAt(i+1)!=xj) i=k[i]; ++i; ++j; if (i>=s) { ++wyn; i=k[i]; } } if (MyNodeId()) { PutInt(0, wyn); Send(0); return 0; } for (int i=1, lw=NumberOfNodes(); i<lw; ++i) { Receive(i); wyn+=GetInt(i); } cout<<wyn<<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 | #include "message.h" #include "poszukiwania.h" #include <iostream> using namespace std; void liczK(int s, int *k) { int i=0, j=k[0]=-1; while (i<s) { int xi=SignalAt(i+1); while (j>-1 && xi!=SignalAt(j+1)) j=k[j]; ++i; ++j; if (i<s && SignalAt(i+1)==SignalAt(j+1)) k[i]=k[j]; else k[i]=j; } } int main() { int s=SignalLength(), m=SeqLength(), *k=new int[s+1], ile=m-s+1; int pocz=ile*(long long) MyNodeId()/NumberOfNodes(), kon=ile*(MyNodeId()+1LL)/NumberOfNodes(); int wyn=0; liczK(s, k); int i=0, j=pocz; kon+=s-1; while (j<kon) { int xj=SeqAt(j+1); while (i>-1 && i<s && SignalAt(i+1)!=xj) i=k[i]; ++i; ++j; if (i>=s) { ++wyn; i=k[i]; } } if (MyNodeId()) { PutInt(0, wyn); Send(0); return 0; } for (int i=1, lw=NumberOfNodes(); i<lw; ++i) { Receive(i); wyn+=GetInt(i); } cout<<wyn<<endl; return 0; } |