Boyer-Moore-Horspool-algoritmi

BMH-algoritmissa ajatellaan, että $P$ on asetettu $S$:n suhteen tietylle kohdalle. Kun halutaan tietää, täsmääkö $P$, vertailu aloitetaan $P$:n loppupäästä ja edetään kohti $P$:n alkua. Jos vuorossa oleva merkkipari ei täsmää, käytetään korjausfunktiota, jolla $P$ siirtyy $1, ..., m$ askelta oikealle. Saadaan algoritmi, joka parhaassa tapauksessa tutkii vain joka $m$:nnen merkin merkkijonossa $S$!

Korjausfunktio perustuu siihen tekstin merkkiin $s_i$, joka on $P$:n viimeisen merkin $P_m$ kohdalla. Mikäli hahmo ei täsmännyt, hahmoa siirretään oikealle siten, että $P$:n viimeisen merkin kohdalla olevan tekstin merkin $s_i$ kohdalle tulee $P$:n lopusta lukien ensimmäinen merkki, joka täsmää $s_i$:n kanssa, taikka koko $P$:n pituuden verran, mikäli $P$ ei sisällä merkkiä $s_i$. Olkoon $d_a=min\{\ t\ \vert\ t=m\ tai\ ( 0 < t < m\ ja\ a=p_{m-t} ) \}$. Tällöin siirron pituuduksi tulee $d_{s_i}$.

Koska siirron pituus riippuu ainoastaan merkistä $s_i$, voidaan tarvittavat siirrot tallentaa taulukkoon, jonka koko on aakkoston koko $\vert\Sigma\vert$. BMH-algoritmia voidaan soveltaa myös suuriin aakkostoihin pilkkomalla aakkoston merkit useammaksi pienemmän aakkoston merkiksi.

BMH-algoritmi vaatii korjausfunktiotaulukolle tilan $O(\vert\Sigma\vert)$. Algoritmin jeskimääräinen aikavaatimus on $O(n/m)$ ja pahimman tapauksen aikavaatimus $O(mn)$.