Haskell Data Analysis Cookbook

Searching a string using the Boyer-Moore-Horspool algorithm

When searching for a pattern in a string, we refer to the pattern as the needle and the whole corpus as the haystack. The Horspool string search algorithm implemented in this recipe performs well for almost all pattern lengths and alphabet sizes, but is ideal for large alphabet sizes and large needle sizes. Empirical benchmarks can be found by navigating to the following URL:

http://orion.lcg.ufrj.br/Dr.Dobbs/books/book5/chap10.htm

By preprocessing the query, the algorithm is able to efficiently skip redundant comparisons. In this recipe, we will implement a simplified version called Horspool's algorithm, which achieves the same average best case as the Boyer-Moore algorithm, benefits ...