Siemka, mam problem z przeniesieniem algorytmu Boyera-Moore do C++. Rozumiem działanie algorytmu, ale jak chce zrobić z niego program w C++, to niestety nic mi nie wychodzi. Mam nadzieję na waszą pomoc(w szczególności od tej części, która miała doczynienia z tym algorytmem) bo sprawa jest pilna. Poniżej opis algorytmu i link do jego szczegółów.Pozdrawiam!
Algorytm Boyera-Moore'a ( w skrócie algorytm BM ) rozpoczyna porównywanie od ostatniego znaku wzorca, czyli odwrotnie niż opisane poprzednio algorytmy. Co nam to daje? Bardzo wiele. Na przykład jeśli ostatni znak wzorca nie zgadza się ze znakiem w przeszukiwanym tekście i dodatkowo wiemy, iż znak z przeszukiwanego tekstu nie występuje dalej we wzorcu, to okno wzorca możemy od razu przesunąć o tyle pozycji, ile znaków zawiera wzorzec. W przeciwnym razie wzorzec pozycjonujemy tak, aby zgrać pozycje znaku występującego jednocześnie w przeszukiwanym tekście i we wzorcu. Algorytmy naiwny i KMP nie pomijają w ten sposób znaków w przeszukiwanym tekście. Dzięki temu algorytm BM zwykle dużo szybciej dochodzi do rozwiązania – mówimy, iż dla typowych danych posiada on podliniową klasę złożoności obliczeniowej. Dla oddania sprawiedliwości należy jednakże zauważyć, iż algorytm KMP nie wymaga buforowania przeglądanego tekstu ( jest to bardzo korzystne w przypadku wykonywania poszukiwań np. w dużych plikach przechowywanych na zewnętrznym nośniku danych – tekst wczytujemy znak po znaku i przetwarzamy ), tymczasem w algorytmie BM takie buforowanie jest konieczne. Jeśli przeszukiwany tekst znajduje się w całości w pamięci operacyjnej komputera, to ograniczenie powyższe nie jest kłopotliwe.
https://eduinf.waw.pl/inf/alg/001_search/0050.php