#include "message.h" #include "poszukiwania.h" #include <iostream> #include <vector> long long int pow (long long int a, long long int x) { long long w = a; for (long long int i = 1; i < x; i++) w *= w; return w; } using namespace std; int main() { int ilosc_czesci = NumberOfNodes() - 1; int signal_length = SignalLength(); int seq_length = SeqLength(); if (ilosc_czesci > seq_length) ilosc_czesci = seq_length; int podstawowa_dlugosc = seq_length / ilosc_czesci; int my_node = MyNodeId(); if (my_node != 0 && my_node <= ilosc_czesci) { // Pobierz wzorzec od 1 + (my_n - 1) * pods_dl // do += podst_dl (lub do konca, dla ostatniego) long long int start_przeszukiwania = 1 + (my_node - 1) * podstawowa_dlugosc; long long int koniec_przeszukiwania = start_przeszukiwania + podstawowa_dlugosc + signal_length - 2; if (koniec_przeszukiwania > seq_length) koniec_przeszukiwania = seq_length; /*vector<int> wzor(signal_length + 1); for (int i = 1; i <= signal_length; i++) wzor[i] = SignalAt(i);*/ // Pobierz tekst od pozycji start_wzorca do (koniec - start_wzorca) /*vector<int> tekst(koniec_przeszukiwania - start_przeszukiwania + 2); for (int i = 0; i <= koniec_przeszukiwania - start_przeszukiwania; i++) { //cout << start_przeszukiwania + i << endl; tekst[i + 1] = SeqAt(start_przeszukiwania + i); }*/ // Przetworz wzorzec na pi vector<int> pi(signal_length + 1); pi[1] = 0; int k = 0; for(int q = 2; q <= signal_length; q++) { while (k > 0 && SignalAt(k + 1) != SignalAt(q)) k = pi[q]; if (SignalAt(k + 1) == SignalAt(q)) k = k + 1; pi[q] = k; } // Odszukaj wzorca w tekscie, zapisz pozycje jego jako: pozycja_znal - dlugosc + start_wzorca long long int pozycje = 0; int q = 0; for (int i = 1; i <= koniec_przeszukiwania - start_przeszukiwania + 1; i++) { while (q > 0 && SignalAt(q + 1) != SeqAt(start_przeszukiwania + i - 1)) q = pi[q]; if (SignalAt(q + 1) == SeqAt(start_przeszukiwania + i - 1)) q = q + 1; if (q == signal_length) { pozycje += 1; //cout << "Znaleziono na poz. " << i - koniec_wzorca + 2 * start_wzorca << endl; q = pi[q]; } } //Wyslij PutLL(0, pozycje); Send(0); } else if (my_node == 0) { // Odbierz od kazdego liste pozycji long long int p = 0; for (int i = 1; i <= ilosc_czesci; i++) { Receive(i); p += GetLL(i); } cout << p; } 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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 | #include "message.h" #include "poszukiwania.h" #include <iostream> #include <vector> long long int pow (long long int a, long long int x) { long long w = a; for (long long int i = 1; i < x; i++) w *= w; return w; } using namespace std; int main() { int ilosc_czesci = NumberOfNodes() - 1; int signal_length = SignalLength(); int seq_length = SeqLength(); if (ilosc_czesci > seq_length) ilosc_czesci = seq_length; int podstawowa_dlugosc = seq_length / ilosc_czesci; int my_node = MyNodeId(); if (my_node != 0 && my_node <= ilosc_czesci) { // Pobierz wzorzec od 1 + (my_n - 1) * pods_dl // do += podst_dl (lub do konca, dla ostatniego) long long int start_przeszukiwania = 1 + (my_node - 1) * podstawowa_dlugosc; long long int koniec_przeszukiwania = start_przeszukiwania + podstawowa_dlugosc + signal_length - 2; if (koniec_przeszukiwania > seq_length) koniec_przeszukiwania = seq_length; /*vector<int> wzor(signal_length + 1); for (int i = 1; i <= signal_length; i++) wzor[i] = SignalAt(i);*/ // Pobierz tekst od pozycji start_wzorca do (koniec - start_wzorca) /*vector<int> tekst(koniec_przeszukiwania - start_przeszukiwania + 2); for (int i = 0; i <= koniec_przeszukiwania - start_przeszukiwania; i++) { //cout << start_przeszukiwania + i << endl; tekst[i + 1] = SeqAt(start_przeszukiwania + i); }*/ // Przetworz wzorzec na pi vector<int> pi(signal_length + 1); pi[1] = 0; int k = 0; for(int q = 2; q <= signal_length; q++) { while (k > 0 && SignalAt(k + 1) != SignalAt(q)) k = pi[q]; if (SignalAt(k + 1) == SignalAt(q)) k = k + 1; pi[q] = k; } // Odszukaj wzorca w tekscie, zapisz pozycje jego jako: pozycja_znal - dlugosc + start_wzorca long long int pozycje = 0; int q = 0; for (int i = 1; i <= koniec_przeszukiwania - start_przeszukiwania + 1; i++) { while (q > 0 && SignalAt(q + 1) != SeqAt(start_przeszukiwania + i - 1)) q = pi[q]; if (SignalAt(q + 1) == SeqAt(start_przeszukiwania + i - 1)) q = q + 1; if (q == signal_length) { pozycje += 1; //cout << "Znaleziono na poz. " << i - koniec_wzorca + 2 * start_wzorca << endl; q = pi[q]; } } //Wyslij PutLL(0, pozycje); Send(0); } else if (my_node == 0) { // Odbierz od kazdego liste pozycji long long int p = 0; for (int i = 1; i <= ilosc_czesci; i++) { Receive(i); p += GetLL(i); } cout << p; } return 0; } |