Algorytm Boyera i Moore'a

Z Wikipedii

Algorytm Boyera i Moore'a – algorytm poszukiwania wzorca w tekście. Dużo prostszy niż np. algorytm Knutha-Morrisa-Pratta. 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 KMP)

[edytuj] 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.