English

Demonstracja działania algorytmu Boyera-Moore'a

Alogrytm Boyera-Moore'a służy do wyszukiwanie krótkiego tekstu, inaczej łańcucha znaków (ozn. x), w innym tek¶cie (ozn. y). Wykorzystywane s± w nim tablice pomocnicze tworzone na podstwie łańcucha x. Szczegółowy opis działania algorytmu znajduje się na stronie Thierry Lecroqa - Boyer-Moore algorithm.
Przykłady (kliknięcie ładuje przykład) ukryj przykłady
x y notatki
gcagagag gcatcgcagagagtatacagtacg przykład ze strony Thierry Lecroqa
acgt agcggagcaacgtccag widać, że przetworzenie wstępne y pozwoliłoby znaleĽć dopasowanie w jednym kroku
agagcag agtggagcaaggaccag wyszukiwanie
agagcag agtggatcaaggaccag wyszukiwanie
11111 7346511119847511111983475 suff
12345 7346512349847512345983475 suff
historia
x y
pokaż szczegóły preprocessingu start wyczy¶ć