Editing Boyer–Moore string-search algorithm (section)

{{Short description|String searching algorithm}}
{{For|the majority vote algorithm|Boyer–Moore majority vote algorithm}}{{For|the Boyer–Moore theorem prover|Nqthm}}
{{Infobox algorithm
|name=Boyer–Moore string search
|class=[[String-searching algorithm|String search]]
|data=[[String (computer science)|String]]
|time=Θ(m) preprocessing + O(mn) matching<ref group="note">''m'' is the length of the pattern string, which we are searching for in the text, which is of length ''n''. This runtime is for finding all occurrences of the pattern, without the Galil rule.</ref>
|best-time=Θ(m) preprocessing + Ω(n/m) matching
|space=Θ(k+m)<ref group="note">''k'' is the size of the alphabet. This space is for the original delta1 bad-character table in the C and Java implementations and the good-suffix table.</ref>
}}
In [[computer science]], the '''Boyer–Moore string-search algorithm''' is an efficient [[string-searching algorithm]] that is the standard benchmark for practical string-search literature.<ref>{{cite journal |last1=Hume |first1=Andrew |last2=Sunday |first2=Daniel |s2cid=5902579 |date=November 1991 |title=Fast String Searching |journal=Software: Practice and Experience |volume=21 |issue=11 |pages=1221–1248 |doi=10.1002/spe.4380211105}}</ref> It was developed by [[Robert S. Boyer]] and [[J Strother Moore]] in 1977.<ref name="original">
{{cite journal
 | last1 = Boyer | first1 = Robert S.
 | author1-link = Robert S. Boyer
 | last2 = Moore | first2 = J Strother
 | author2-link = J Strother Moore
 | title = A Fast String Searching Algorithm.
 | journal = Comm. ACM
 | volume = 20
 | issue = 10
 | pages = 762–772
 | publisher = Association for Computing Machinery
 | location = New York
 | date = October 1977
 | issn = 0001-0782
 | doi = 10.1145/359842.359859 | s2cid = 15892987
 | doi-access = free
 }}
</ref> The original paper contained static tables for computing the pattern shifts without an explanation of how to produce them. The algorithm for producing the tables was published in a follow-on paper; this paper contained errors which were later corrected by [[Wojciech Rytter]] in 1980.<ref name="Knuth_Morris_Pratt">{{cite journal |last1=Knuth |first1=Donald E. |author1-link=Donald Knuth |last2=Morris |first2=James H. Jr. |author2-link=James H. Morris |last3=Pratt |first3=Vaughan R. |author3-link=Vaughan Pratt |title=Fast pattern matching in strings |journal=SIAM Journal on Computing |issn=0097-5397 |volume=6 |issue=2 |pages=323–350 |year=1977 |url=http://citeseer.ist.psu.edu/context/23820/0 |doi=10.1137/0206024 |citeseerx=10.1.1.93.8147}}</ref><ref name="Rytter1980">{{cite journal|last1=Rytter|first1=Wojciech|title=A Correct Preprocessing Algorithm for Boyer–Moore String-Searching|journal=SIAM Journal on Computing|volume=9|issue=3|year=1980|pages=509–512|issn=0097-5397|doi=10.1137/0209037}}</ref>

The algorithm [[preprocessor|preprocesses]] the [[string (computer science)|string]] being searched for (the pattern), but not the string being searched in (the text). It is thus well-suited for applications in which the pattern is much shorter than the text or where it persists across multiple searches. The Boyer–Moore algorithm uses information gathered during the preprocess step to skip sections of the text, resulting in a lower constant factor than many other string search algorithms. In general, the algorithm runs faster as the pattern length increases. The key features of the algorithm are to match on the tail of the pattern rather than the head, and to skip along the text in jumps of multiple characters rather than searching every single character in the text.