Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Boyer–Moore–Horspool algorithm
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, the Boyer–Moore–Horspool algorithm or Horspool's algorithm is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> for finding <a href="/facts/Substring/dM5Rqg6X">substrings</a> in <a href="/facts/String_(computer_science)/4ChJu5WS">strings</a>. It was published by <a href="/facts/Nigel_Horspool/uzl497aK">Nigel Horspool</a> in 1980 as SBM. </p><p>It is a simplification of the <a href="/facts/Boyer%E2%80%93Moore_string-search_algorithm/yUGSAvN6">Boyer–Moore string-search algorithm</a> which is related to the <a href="/facts/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm/A4uM3D8e">Knuth–Morris–Pratt algorithm</a>. The algorithm trades space for time in order to obtain an <a href="/facts/Average-case_complexity/6TqLIMMz">average-case complexity</a> of <i>O(n)</i> on random text, although it has <i>O(nm)</i> in the <a href="/facts/Worst_case/Ed9ekH30">worst case</a>, where the length of the pattern is <i>m</i> and the length of the search string is <i>n</i>. </p>