Average running time of the Boyer-Moore-Horspool algorithm

DOI10.1016/0304-3975(92)90133-ZzbMath0747.68020OpenAlexW2009334077WikidataQ127740123 ScholiaQ127740123MaRDI QIDQ1190450

Mireille Régnier, Ricardo A. Baeza-Yates

Publication date: 26 September 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90133-z

zbMATH Keywords

linear time algorithmstring matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Related Items

Speeding up two string-matching algorithms, On Boyer-Moore automata, The Boyer-Moore-Horspool heuristic with Markovian input, On modification of Boyer-Moore-Horspool's algorithm for tree pattern matching in linearised trees, Algorithms in the Ultra-Wide Word Model, Optimal pattern matching algorithms, An algorithm to compute the character access count distribution for pattern matching algorithms, Designing optimal- and fast-on-average pattern matching algorithms, Improved pattern-scan-order algorithms for string matching, Analysis of Boyer-Moore-Horspool string-matching heuristic, Regular Expressions at Their Best: A Case for Rational Design, Fast string matching for DNA sequences, Speeding up two string-matching algorithms

Cites Work

• An analytical comparison of two string searching algorithms
• On the Expected Sublinearity of the Boyer–Moore Algorithm
• The Complexity of Pattern Matching for a Random String
• On the Worst-Case Behavior of String-Searching Algorithms
• Fast Pattern Matching in Strings
• Fast algorithms for two dimensional and multiple pattern matching
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item