In computer science, the BoyerMooreHorspool algorithm or Horspool's algorithm is an algorithm for finding substrings in strings. It was published by Nigel Horspool in 1980. It is a simplification of the BoyerMoore string search algorithm which is related to the KnuthMorrisPratt 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, where the length of the pattern is M and the length of the search string is N. Like BoyerMoore, BoyerMooreHorspool preprocesses the pattern to produce a table containing, for each symbol in the alphabet, the number of characters that can safely be skipped. The preprocessing phase, in pseudocode, is as follows (for an alphabet of 256 symbols, i.e., bytes): Pattern search proceeds as follows. [ disputed discuss ] The procedure search reports the index of the first occurrence of needle in haystack . https://en.wikipedia.org/wiki/Boyer%E2%80%93Moor...