A variation on the Boyer-Moore algorithm

DOI10.1016/0304-3975(92)90139-7zbMath0747.68023OpenAlexW2100810239MaRDI QIDQ1190458

Thierry Lecroq

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)90139-7

zbMATH Keywords

linear- time algorithmBoyer-Moore automatonlongest prefix of the wordquadratic worst-case running timesmallest suffix automaton

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-line string matching algorithms: survey and experimental results, On the string matching with \(k\) mismatches, The wide window string matching algorithm, Finite Automata for Generalized Approach to Backward Pattern Matching, Speeding up two string-matching algorithms

Cites Work

• The smallest automaton recognizing the subwords of a text
• On Boyer-Moore automata
• Transducers and repetitions
• On improving the worst case running time of the Boyer-Moore string matching algorithm
• A fast string searching algorithm
• The Boyer–Moore–Galil String Searching Strategies Revisited
• A Correct Preprocessing Algorithm for Boyer–Moore String-Searching
• A New Proof of the Linearity of the Boyer-Moore String Searching Algorithm
• Fast Pattern Matching in Strings
• Unnamed Item
• Unnamed Item
• Unnamed Item