Algorytm Boyera i Moore'a – algorytm poszukiwania wzorca w tekście. Polega na porównywaniu, zaczynając od ostatniego elementu wzorca.
Zalety:
- jeżeli okaże się, że znak, który aktualnie sprawdzamy, nie należy do wzorca możemy przeskoczyć w analizie tekstu o całą długość wzorca
- z reguły skoki wzorca są większe od 1 (można porównać z algorytmem Knutha-Morrisa-Pratta)
Przykłady
tekst: WIKIPEDIA, WOLNA ENCYKLOPEDIA wzorzec: CYKL
WIKIPEDIA, WOLNA ENCYKLOPEDIA
| | | | | |
CYKL | | | | |
CYKL | | | |
CYKL | | |
CYKL | |
CYKL |
CYKL
Pierwsze 4 porównania trafiają na litery: i, i, w, a, które nie występują we wzorcu, możemy więc za każdym razem skoczyć do przodu o całą długość wzorca, a więc 4 znaki. Kolejne porównanie trafia jednak na literę 'c', która występuje we wzorcu. Należy wówczas przesunąć wzorzec tak, by litery te nałożyły się na siebie. W tym przypadku okazuje się, że natrafiliśmy na szukane słowo.
tekst: ALGORYTMY I STRUKTURY DANYCH wzorzec: TUR
ALGORYTMY I STRUKTURY DANYCH
| | | | | | |
TUR | | | | | |
TUR | | | | |
TUR | | | |
TUR | | |
TUR | |
TUR |
TUR
Pierwsze 4 porównania trafiają na litery: g, y, y, 'spacja', które nie występują we wzorcu, możemy więc skoczyć o całą długość wzorca do przodu. Przy 5 porównaniu litera, którą sprawdzamy, znajduje się we wzorcu. W tym przypadku nie przesuwamy wzorca do przodu, ponieważ litery już się pokrywają. Sprawdzamy kolejne litery. Okazuje się jednak, że już się nie pokrywają, więc znów możemy skoczyć o całą długość wzorca. Natrafiamy na literę 't', która znajduje się we wzorcu. Przesuwamy wzorzec tak by litery pokrywały się. Tym razem znaleźliśmy szukane słowo.