Boyer–Moore string-search algorithm
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. It was developed by Robert S. Boyer and J Strother Moore in 1977. 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. The algorithm preprocesses the 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 alg
- BestTime
- enΘ preprocessing + Ω matching
- Class
- String-searching algorithm
- Comment
- enIn computer science, the Boyer–Moore string-search algorithm is an efficient string-searching algorithm that is the standard benchmark for practical string-search literature. It was developed by Robert S. Boyer and J Strother Moore in 1977. 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. The algorithm preprocesses the 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 alg
- Data
- String (computer science)
- Has abstract
- enIn computer science, the Boyer–Moore string-search algorithm is an efficient string-searching algorithm that is the standard benchmark for practical string-search literature. It was developed by Robert S. Boyer and J Strother Moore in 1977. 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. The algorithm preprocesses the 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.
- Is primary topic of
- Boyer–Moore string-search algorithm
- Label
- enBoyer–Moore string-search algorithm
- Link from a Wikipage to an external page
- www.cs.nyu.edu/cs/faculty/cole/papers/CHPZ95.ps
- www.cs.utexas.edu/~moore/publications/fstrpos.pdf
- www.cs.utexas.edu/users/moore/best-ideas/string-searching/fstrpos-example.html
- yurichev.com/news/20210421_boyer_moore/
- golang.org/src/strings/search.go
- www.boost.org/doc/libs/1_58_0/libs/algorithm/doc/html/algorithm/Searching.html%23the_boost_algorithm_library.Searching.BoyerMoore
- dlang.org/phobos/std_algorithm_searching.html%23boyerMooreFinder
- Link from a Wikipage to another Wikipage
- %5D for a in range(ALPHABET SIZE)%5D
- -1%5D for a in range(ALPHABET SIZE)%5D
- Algorithm
- Andrew Odlyzko
- Apostolico–Giancarlo algorithm
- Boost (C++ libraries)
- Boyer–Moore–Horspool algorithm
- Brute-force search
- C++
- Category:Articles with example C code
- Category:Articles with example Java code
- Category:Articles with example Python (programming language) code
- Category:String matching algorithms
- Computer science
- D (programming language)
- Donald Knuth
- Galil rule
- GNU
- Go (programming language)
- Grep
- James H. Morris
- J Strother Moore
- Leonidas J. Guibas
- Preprocessor
- Raita algorithm
- Richard J. Cole
- Robert S. Boyer
- String (computer science)
- String-searching algorithm
- Substring
- Vaughan Pratt
- Wojciech Rytter
- Zvi Galil
- Name
- enBoyer–Moore string search
- SameAs
- 53WmJ
- Algorithme de Boyer-Moore
- Algoritma Boyer-Moore
- Algoritmo de busca de expressões Boyer-Moore
- Algoritmo de búsqueda de cadenas Boyer-Moore
- Algoritmo di Boyer-Moore
- Algorytm Boyera i Moore’a
- Blogo simbolio taisyklė
- Boyer-Moore-Algorithmus
- Q895984
- Алгоритм Бойера — Мура
- Алгоритм Боєра — Мура
- Бојер-Мур алгоритам за претрагу ниски
- אלגוריתם בויאר-מור
- الگوریتم بویر مور
- ขั้นตอนวิธีค้นหาสายอักขระบอยเยอร์–มัวร์
- ボイヤー-ムーア文字列検索アルゴリズム
- 博耶-穆尔字符串搜索算法
- Side
- enright
- Space
- enΘ
- Subject
- Category:Articles with example C code
- Category:Articles with example Java code
- Category:Articles with example Python (programming language) code
- Category:String matching algorithms
- Time
- enΘ preprocessing + O matching
- WasDerivedFrom
- Boyer–Moore string-search algorithm?oldid=1100446170&ns=0
- Width
- 340
- 380
- WikiPageLength
- 35779
- Wikipage page ID
- 684709
- Wikipage revision ID
- 1100446170
- WikiPageUsesTemplate
- Template:=
- Template:Commons category
- Template:Float begin
- Template:Float end
- Template:For
- Template:Infobox algorithm
- Template:Math
- Template:Mvar
- Template:Reflist
- Template:Short description
- Template:Strings
- Template:Tmath