Difference between original Boyer–Moore and Boyer–Moore–Horspool Algorithm

Question

I am not able to understand the changes which Horspool made in his algorithm. If you have any link of Boyer–Moore–Horspool algorithm then please do tell me.

Answer 1

Here are my few observations:

BM:

Preprocessing complexity: Θ(m + σ)

Worst Case : Θ(nm) If pattern exists Θ(n+m) If pattern doesn't exist" 
Best Case : Θ(n/m) 
Space: Θ(σ) 
Comparisions: Θ(3n)

Preprocessing: Uses Good Suffix and Bad Character Shift.
At every step, it slides the pattern by the max of the slides suggested by 
the two heuristics. So it uses best of the two heuristics at every step.

Boyer Moore algorithm uses the "bad" text character itself to determine the 
shift distance.

Probably the fastest non-indexed text-search algorithm known.  
Works better in natural text and larger text searches.

A little difficult to implement.

Mostly used.

BMH:

Preprocessing complexity : Θ(m + σ)

Worst Case : Θ(nm)
Best Case : Θ(n)
Space : Θ(σ)
Comparisons : Θ(1/σ) to Θ(2/σ+1)

Preprocessing:

Recommends to Use only Bad Character Shift.
uses the rightmost character of the current text window to determine the 
shift distance.

Efficient for small alphabets

Easy to implement.