GPTKB
Browse
Query
Compare
Download
Publications
Contributors
Search
Boyer–Moore string-search algorithm
URI:
https://gptkb.org/entity/Boyer–Moore_string-search_algorithm
GPTKB entity
Statements (29)
Predicate
Object
gptkbp:instanceOf
string-search algorithm
gptkbp:application
search engines
text editors
pattern matching
gptkbp:averageCaseComplexity
O(n)
gptkbp:bestCaseComplexity
O(n/m)
gptkbp:field
computer science
algorithms
string matching
gptkbp:hasWikipediaPage
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm
https://www.w3.org/2000/01/rdf-schema#label
Boyer–Moore string-search algorithm
gptkbp:influenced
gptkb:Knuth–Morris–Pratt_algorithm
gptkb:Boyer–Moore_majority_vote_algorithm
gptkb:Boyer–Moore–Horspool_algorithm
gptkbp:introducedIn
1977
gptkbp:inventedBy
gptkb:J_Strother_Moore
gptkb:Robert_S._Boyer
gptkbp:language
English
gptkbp:notableFor
efficient practical performance
skipping sections of text
sublinear time complexity in practice
gptkbp:publishedIn
gptkb:SIAM_Journal_on_Computing
gptkbp:usesHeuristic
bad character rule
good suffix rule
gptkbp:worstCaseComplexity
O(nm)
gptkbp:bfsParent
gptkb:J_Strother_Moore
gptkb:Robert_S._Boyer
gptkb:Robert_H._Boyer
gptkbp:bfsLayer
7