Horspool's algorithm for string matching

Horspool's algorithm is an algorithm for finding substrings in strings.

It is a simplification of the Boyer-Moore algorithm which is related to the Knuth-Morris-Pratt algorithm. The algorithm trades space for time in order to obtain an average case complexity of

O(N)

on random text, although it has

O(MN)

in the worst case.