A variation on the Boyer-Moore algorithm

DOI10.1016/0304-3975(92)90139-7MaRDI QIDQ1190458zbMATH OpenOpenAlexFDO

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

Recommendations

• On Boyer-Moore automata
• On the size of Boyer-Moore automata
• scientific article; zbMATH DE number 8792
• A unifying look at the Apostolico--Giancarlo string-matching algorithm
• A Boyer-Moore type string matching algorithm with memory and its computational complexity

Cites work

• scientific article; zbMATH DE number 432823 (Why is no real title available?)
• scientific article; zbMATH DE number 8792 (Why is no real title available?)
• scientific article; zbMATH DE number 1142294 (Why is no real title available?)
• A Correct Preprocessing Algorithm for Boyer–Moore String-Searching
• A New Proof of the Linearity of the Boyer-Moore String Searching Algorithm
• A fast string searching algorithm
• Fast Pattern Matching in Strings
• On Boyer-Moore automata
• On improving the worst case running time of the Boyer-Moore string matching algorithm
• The Boyer–Moore–Galil String Searching Strategies Revisited
• The smallest automaton recognizing the subwords of a text
• Transducers and repetitions

Cited in

(9)

• On-line string matching algorithms: survey and experimental results
• Speeding up two string-matching algorithms
• The wide window string matching algorithm
• Speeding up two string-matching algorithms
• scientific article; zbMATH DE number 6117079 (Why is no real title available?)
• Finite automata for generalized approach to backward pattern matching
• scientific article; zbMATH DE number 6585 (Why is no real title available?)
• On the string matching with \(k\) mismatches
• A Variant of the F4 Algorithm

This page was built for publication: A variation on the Boyer-Moore algorithm

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