原始 Boyer-Moore 和 Boyer-Moore-Horspool 算法的区别

Question

我无法理解 Horspool 在他的算法中所做的更改。如果您有 Boyer-Moore-Horspool 算法的任何链接，请告诉我。

Answer 1

以下是我的一些观察：

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.