Przeszukiwanie wzorca.

pytanie zadane 26 stycznia 2018 w Rozwój zawodowy, nauka, praca przez Piotrek Rybarczyk Nowicjusz (230 p.)

Witam mam mały problem z dwoma zadaniami dotyczącymi przeszukiwania wzorca a dokładniej chodzi o algorytm KMP oraz Boyera-Moore'a. Męczę się już z tym trochę i nie wiem czy dobrze myślę. Znajdzie się ktoś kto mógłby mi pomóc ?

komentarz 26 stycznia 2018 przez CenterPL Pasjonat (19,070 p.)

W czym problem? Co już zrobiłeś? Pokaż kod czy to co tam masz zrobić.

komentarz 26 stycznia 2018 przez Piotrek Rybarczyk Nowicjusz (230 p.)

To akurat nie ma być kod tylko trzeba przedstawić jak zachowują się te dwa algorytmy. Tutaj mam trochę zad 1 ale nawet nie wiem czy dobrze to robię.

komentarz 26 stycznia 2018 przez CenterPL Pasjonat (19,070 p.)

Czy w przypadku algorytmu Boyera-Moore'a nie sprawdzamy znaku na ostatniej pozycji? Ogólnie to co zrobiłeś jest jakby okej, ale gdy masz ciąg ASXSSDX to szukasz X w ciągu bazowym. I teraz jeżeli litera, którą sprawdzasz nie należy do ciągu który szukasz, przeskakujesz o długość ciągu poszukiwanego. Jeżeli natomiast trafiasz na znak, który jest w ciągu szukanym, przesuwasz tak aby litery te na siebie się nałożyły.

0)XSXAASXSSDXDDADXXSSADASXSSDX
1)ASXSSDX
2)--------------ASXSSDX
3)----------------------------ASXSSDX
4)------------------------------------------ASXSSDX

1) Mamy X i trafiamy na samym początku X, sprawdzamy więc pozostałe litery - nie zgadzają się.

2) Przesuwamy ciąg o całą długość- ostatnia litera się nie zgadza

3) Przesuwamy ciąg o całą długość- ostatnia litera się nie zgadza

4) Przesuwamy ciąg o całą długość - ostatnia litera się zgadza, sprawdzam kolejną, zgadza się, i kolejne również. Ciąg został znaleziony, koniec algorytmu.

Na 90% tak to działa.

Drugiego algorytmu nie znam, ale Google i do boju: http://eduinf.waw.pl/inf/alg/001_search/0049.php