#include "poszukiwania.h" #include "message.h" #include <iostream> using namespace std; void KMP(unsigned int * Pref, int n){ Pref[0] = 0; int t = Pref[0]; for (int i = 1; i < n; i++) { while (t > 0 && SignalAt(i+1) != SignalAt(t+1) ) t=Pref[t+1]; if(SignalAt(i+1) == SignalAt(t+1)) t++; Pref[i] = t; } } unsigned int KMP2(unsigned int * Pref, int n, int m){ int licznik=0; int t=0; for (int i = 0; i < n; i++) { while (t > 0 && SeqAt(i+1) != SignalAt(t+1) ) t=Pref[t-1]; if(SignalAt(t+1) == SeqAt(i+1)) t++; if(t==m){ licznik++; t=Pref[t-1]; } } return licznik; } unsigned int KMP3(unsigned int * Pref, int i1, int i2, int m){ int licznik=0; int t=0; for (int i = i1; i < i2; i++) { while (t > 0 && SeqAt(i+1) != SignalAt(t+1) ) t=Pref[t-1]; if(SignalAt(t+1) == SeqAt(i+1)) t++; if(t==m){ licznik++; t=Pref[t-1]; } } return licznik; } int main() { unsigned int n, m; n=SeqLength(); m=SignalLength(); unsigned int*pref = new unsigned int[m+1]; pref[m]=0; if(n<=20000000){ if(MyNodeId()==0){ KMP(pref, m); cout << KMP2(pref, n, m); } } else if(m<=50000000){ KMP(pref, m); int i1=MyNodeId()*n/NumberOfNodes(); int i2=min((MyNodeId()+1)*n/NumberOfNodes()-1+m, n); int moj_wynik=KMP3(pref, i1, i2, m); //cout << moj_wynik; if(MyNodeId()!=0){ PutInt(0, moj_wynik); Send(0); } else{ int wynik_razem=moj_wynik; for(int i=1; i<NumberOfNodes(); i++){ Receive(i); wynik_razem+=GetInt(i); } cout << wynik_razem; } } 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 71 72 73 74 75 76 77 78 79 80 | #include "poszukiwania.h" #include "message.h" #include <iostream> using namespace std; void KMP(unsigned int * Pref, int n){ Pref[0] = 0; int t = Pref[0]; for (int i = 1; i < n; i++) { while (t > 0 && SignalAt(i+1) != SignalAt(t+1) ) t=Pref[t+1]; if(SignalAt(i+1) == SignalAt(t+1)) t++; Pref[i] = t; } } unsigned int KMP2(unsigned int * Pref, int n, int m){ int licznik=0; int t=0; for (int i = 0; i < n; i++) { while (t > 0 && SeqAt(i+1) != SignalAt(t+1) ) t=Pref[t-1]; if(SignalAt(t+1) == SeqAt(i+1)) t++; if(t==m){ licznik++; t=Pref[t-1]; } } return licznik; } unsigned int KMP3(unsigned int * Pref, int i1, int i2, int m){ int licznik=0; int t=0; for (int i = i1; i < i2; i++) { while (t > 0 && SeqAt(i+1) != SignalAt(t+1) ) t=Pref[t-1]; if(SignalAt(t+1) == SeqAt(i+1)) t++; if(t==m){ licznik++; t=Pref[t-1]; } } return licznik; } int main() { unsigned int n, m; n=SeqLength(); m=SignalLength(); unsigned int*pref = new unsigned int[m+1]; pref[m]=0; if(n<=20000000){ if(MyNodeId()==0){ KMP(pref, m); cout << KMP2(pref, n, m); } } else if(m<=50000000){ KMP(pref, m); int i1=MyNodeId()*n/NumberOfNodes(); int i2=min((MyNodeId()+1)*n/NumberOfNodes()-1+m, n); int moj_wynik=KMP3(pref, i1, i2, m); //cout << moj_wynik; if(MyNodeId()!=0){ PutInt(0, moj_wynik); Send(0); } else{ int wynik_razem=moj_wynik; for(int i=1; i<NumberOfNodes(); i++){ Receive(i); wynik_razem+=GetInt(i); } cout << wynik_razem; } } return 0; } |