• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Przeszukiwanie wzorca.

VPS Starter Arubacloud
0 głosów
344 wizyt
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
komentarz 26 stycznia 2018 przez Piotrek Rybarczyk Nowicjusz (230 p.)
OK dzięki :D

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

0 głosów
3 odpowiedzi 1,004 wizyt
0 głosów
1 odpowiedź 108 wizyt
0 głosów
3 odpowiedzi 561 wizyt
pytanie zadane 22 maja 2018 w C i C++ przez kamila131 Nowicjusz (140 p.)

92,845 zapytań

141,786 odpowiedzi

320,861 komentarzy

62,178 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Wprowadzenie do ITsec, tom 2

Można już zamawiać tom 2 książki "Wprowadzenie do bezpieczeństwa IT" - będzie to około 650 stron wiedzy o ITsec (17 rozdziałów, 14 autorów, kolorowy druk).

Planowana premiera: 30.09.2024, zaś planowana wysyłka nastąpi w drugim tygodniu października 2024.

Warto preorderować, tym bardziej, iż mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy dodatkowe 15% zniżki! Dziękujemy zaprzyjaźnionej ekipie Sekuraka za kod dla naszej Społeczności!

...