本文介绍了原始Boyer-Moore和Boyer-Moore-Horspool算法之间的区别的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我无法理解Horspool在他的算法中所做的更改。如果您有Boyer–Moore–Horspool算法的任何链接,请告诉我。
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.
推荐答案以下是我的一些观察结果:
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.更多推荐
原始Boyer
发布评论