On the Expected Sublinearity of the Boyer–Moore Algorithm

DOI10.1137/0217041MaRDI QIDQ3796763zbMATH OpenOpenAlexFDO

Authors Robert Schaback

Publication date 1988

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0217041

zbMATH Keywords

average case analysis of algorithmsBoyer-Moore string-matching algorithmpattern matchingstring searching

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Pattern recognition, speech recognition (68T10)

Recommendations

• Fast string matching in stationary ergodic sources
• Fastest Pattern Matching in Strings
• Average running time of the Boyer-Moore-Horspool algorithm
• scientific article; zbMATH DE number 4045218
• Analysis of Boyer-Moore-Horspool string-matching heuristic

Cited in

(8)

• Average running time of the Boyer-Moore-Horspool algorithm
• An algorithm to compute the character access count distribution for pattern matching algorithms
• The Boyer-Moore-Horspool heuristic with Markovian input
• Fast string matching in stationary ergodic sources
• Analysis of Boyer-Moore-Horspool string-matching heuristic
• scientific article; zbMATH DE number 1953284 (Why is no real title available?)
• Average case analysis of the Boyer‐Moore algorithm
• A unifying look at the Apostolico--Giancarlo string-matching algorithm

This page was built for publication: On the Expected Sublinearity of the Boyer–Moore Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3796763)