In computer science, the Boyer–Moore–Horspool algorithm or Horspool's algorithm is an algorithm for finding substrings in strings. It was published by Nigel Horspool in 1980 as SBM. It is a simplification of the Boyer–Moore string-search 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(nm) in the worst case, where the length of the pattern is m and the length of the search string is n. Description Like Boyer–Moore, Boyer–Moore–Horspool 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): Unlike the original, we use zero-based indices here. function preprocess(pattern) T ← new table of 256 integers for i from 0 to 256 exclusive T[i] ← length(pattern) for i from 0 to length(pattern) - 1 exclusive T[pattern[i]] ← length(pattern) - 1 - i return T Pattern search proceeds as follows. The procedure reports the index of the first occurrence of in . function same(str1, str2, len) Compares two strings, up to the first len characters. i ← len - 1 while str1[i] = str2[i] Note: this is equivalent to !memcmp(str1, str2, len). if i = 0 The original algorithm tries to play smart here: it checks for the return true last character, and then starts from the first to the second-last. i ← i - 1 return false function search(needle, haystack) T ← preprocess(needle) skip ← 0 while length(haystack) - skip ≥ length(needle) haystack[skip:] -- substring starting with "skip". &haystack[skip] in C. if same(haystack[skip:], needle, length(needle)) return skip skip ← skip + T[haystack[skip + length(needle) - 1]] return not-found Performance The algorithm performs best with long needle strings, when it consistently hits a non-matching character at or near the final byte of the current position in the haystack and the final byte of the needle does not occur elsewhere within the needle. For instance a 32 byte needle ending in "z" searching through a 255 byte haystack which does not have a 'z' byte in it would take up to 224 byte comparisons. The best case is the same as for the Boyer–Moore string-search algorithm in big O notation, although the constant overhead of initialization and for each loop is less.