Boyer Moore (övning 6)

Tidskomplexiteten för sökning är O(n+m) där

n = antal tecken i texten

m = antal tecken i söksträngen.

Anta att vi söker efter "AGCTG" i texten "TACCGATGACCGAGTTAAGCTAGCATTGACGTGAGCTAGTATCAAGTAGACTAGATTCATACGT"

Då är n = 64 och m = 5. Både söksträngen och texten vi söker i innehåller bara fyra olika tecken, A, T, C och G så det är ganska stor chans att vi får en träff när vi jämför.

Men i bästa fall kan Boyer Moore ge O(n/m) jämförelser, om texten vi söker i har stor variation. Då är chansen för en träff mycket mindre, så vi kommer oftast att kunna hoppa fram m steg i texten.