Vyhledávání Boyer-Moore

O(n·m) worst, sublinear typical

Boyer-Moore je matcher, který reálně používá většina textových editorů, protože obvykle prozkoumá jen zlomek textu. Zarovná vzor a porovnává zprava doleva. Při neshodě použije pravidlo špatného znaku: vyhledá neshodný znak textu ve vzoru a posune vzor tak, aby se zarovnal jeho poslední výskyt — a pokud znak ve vzoru vůbec není, přeskočí celý vzor za něj. Tyhle skoky mohou být velké, takže čím rozmanitější abeceda, tím rychleji běží (na typickém textu sublineárně, v nejhorším případě ale O(n·m)). Plný algoritmus přidává i pravidlo dobrého sufixu; tady je klasická verze se špatným znakem. Shodný sufix je teal, aktuální porovnání oranžové, neshody červené a potvrzené shody zelené.

Text a vzor
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Sestav tabulku špatného znaku: poslední index každého znaku ve vzoru.
  2. Zarovnej vzor a porovnávej s textem zprava doleva.
  3. Při neshodě posuň vzor tak, aby problematický znak textu potkal svůj poslední výskyt.
  4. Pokud znak ve vzoru není, přeskoč celý vzor za něj; při úplné shodě zaznamenej a posuň se.

Pseudokód

1boyerMoore(text, pattern):          # sublinear typical2  last[c] = last index of c in pattern (bad-char table)3  align pattern at s = 04  while s ≤ n - m:5    compare pattern with text RIGHT to LEFT6    on mismatch of text char c at pattern j:7      s += max(1, j − last[c])       # jump past8    on full match: record it, s += 1