title: Which is a better string searching algorithm? Boyer-Moore or Boyer Moore Horspool?
body: <p>The Boyer Moore algorithm has a a preprocessing time of Θ(m + |Σ|) and a matching time of Ω(n/m), O(n). I understand that Boyer Moore Horspool is an advancement of Simplified Boyer Moore itself, however its average case complexity is O(N) and worst case O(MN) according to <a href="http://en.wikipedia.org/wiki/Boyer-Moore-Horspool_algorithm" rel="nofollow">this Wikipedia article</a>. So in the worst case it should be slower than the Boyer Moore algorithm. But <a href="http://orion.lcg.ufrj.br/Dr.Dobbs/books/book5/chap10.htm" rel="nofollow">this classic survey</a> by University of Chile shows that the Boyer-Moore horspool outperforms Boyer Moore almost every time. I am confused! Which one should I use (for small as well as large patterns) for string searching and which algorithm has a greater significance in the practical world (I am just a Computer science student)?</p>