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.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Boyer–Moore–Horspool algorithm (en)
- Algorithme de Boyer-Moore-Horspool (fr)
- Алгоритм Бойера — Мура — Хорспула (ru)
- Алгоритм Бойєра — Мура — Хорспула (uk)
|
| rdfs:comment
| - 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. (en)
- L'algorithme de Boyer-Moore-Horspool ou Horspool est un algorithme de recherche de sous-chaîne publié par en 1980. Il consiste en une simplification de l’algorithme de Boyer-Moore qui ne garde que la première table de saut. On notera T le texte de recherche, P la sous-chaîne recherchée et ∑ l'alphabet. (fr)
- Алгоритм Бойера — Мура — Хорспула — алгоритм поиска подстроки в строке, упрощённый вариант алгоритма Бойера — Мура. АБМХ работает лучше алгоритма Бойера — Мура на случайных текстах, оценка в среднем от до на один символ текста. К тому же, требующая многих предварительных вычислений эвристика совпавшего суффикса опускается. Впрочем, оценка (в худшем случае на непериодических шаблонах) у АБМХ составляет |needle|·|haystack| (вместо 3|haystack| у Бойера-Мура). (ru)
- Алгоритм Бойєра — Мура — Хорспула — алгоритм пошуку рядка — спрощений варіант алгоритму Бойера — Мура. АБМХ працює краще алгоритму Бояра — Мура на випадкових текстах. До того ж, вимагає багатьох попередніх обчислень евристика збіглася суфікса опускається. (uk)
|
| dct:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| class
| |
| data
| |
| has abstract
| - 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. (en)
- L'algorithme de Boyer-Moore-Horspool ou Horspool est un algorithme de recherche de sous-chaîne publié par en 1980. Il consiste en une simplification de l’algorithme de Boyer-Moore qui ne garde que la première table de saut. On notera T le texte de recherche, P la sous-chaîne recherchée et ∑ l'alphabet. (fr)
- Алгоритм Бойера — Мура — Хорспула — алгоритм поиска подстроки в строке, упрощённый вариант алгоритма Бойера — Мура. АБМХ работает лучше алгоритма Бойера — Мура на случайных текстах, оценка в среднем от до на один символ текста. К тому же, требующая многих предварительных вычислений эвристика совпавшего суффикса опускается. Впрочем, оценка (в худшем случае на непериодических шаблонах) у АБМХ составляет |needle|·|haystack| (вместо 3|haystack| у Бойера-Мура). (ru)
- Алгоритм Бойєра — Мура — Хорспула — алгоритм пошуку рядка — спрощений варіант алгоритму Бойера — Мура. АБМХ працює краще алгоритму Бояра — Мура на випадкових текстах. До того ж, вимагає багатьох попередніх обчислень евристика збіглася суфікса опускається. (uk)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is Wikipage disambiguates
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)