A New Proof of the Linearity of the Boyer-Moore String Searching Algorithm

DOI10.1137/0209051zbMath0446.68050OpenAlexW2054762052MaRDI QIDQ3891777

Andrew M. Odlyzko, Leonidas J. Guibas

Publication date: 1980

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

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

zbMATH Keywords

pattern matchingalgorithmic analysisBoyer-Moore string searching

Mathematics Subject Classification ID

Searching and sorting (68P10) Information storage and retrieval of data (68P20)

Related Items

Speeding up two string-matching algorithms ⋮ On Boyer-Moore automata ⋮ Light-based string matching ⋮ A unifying look at the Apostolico--Giancarlo string-matching algorithm ⋮ String overlaps, pattern matching, and nontransitive games ⋮ Periods in strings ⋮ Correctness and efficiency of pattern matching algorithms ⋮ A variation on the Boyer-Moore algorithm ⋮ Fast String Matching in Stationary Ergodic Sources ⋮ Speeding up two string-matching algorithms