Speeding up two string-matching algorithms

DOI10.1007/BF01185427zbMath0942.68574OpenAlexW1992020000WikidataQ60163036 ScholiaQ60163036MaRDI QIDQ1336956

Leszek Gąsieniec, Maxime Crochemore, Wojciech Rytter, Wojciech Plandowski, Stefan Jarominek, Thierry Lecroq, Artur Czumaj

Publication date: 26 February 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01185427

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Parallel algorithms in computer science (68W10) Information storage and retrieval of data (68P20) Computing methodologies for text processing; mathematical typography (68U15)

Related Items (37)

Tight bounds on the complexity of the Apostolico-Giancarlo algorithm ⋮ Average complexity of exact and approximate multiple string matching ⋮ Light-based string matching ⋮ Accelerating Boyer-Moore searches on binary texts ⋮ Efficient parameterized string matching ⋮ Saving comparisons in the Crochemore-Perrin string-matching algorithm ⋮ A Bit-Parallel Exact String Matching Algorithm for Small Alphabet ⋮ A unifying look at the Apostolico--Giancarlo string-matching algorithm ⋮ Practical and flexible pattern matching over Ziv-Lempel compressed text. ⋮ Fast and flexible packed string matching ⋮ Accelerating Boyer Moore Searches on Binary Texts ⋮ Improved characters distance sampling for online and offline text searching ⋮ String matching with alphabet sampling ⋮ Average complexity of backward \(q\)-gram string matching algorithms ⋮ Efficient online string matching based on characters distance text sampling ⋮ Worst-case efficient single and multiple string matching on packed texts in the word-RAM model ⋮ A simple fast hybrid pattern-matching algorithm ⋮ Fast Average-Case Pattern Matching on Weighted Sequences ⋮ On-line string matching algorithms: survey and experimental results ⋮ Linear and Efficient String Matching Algorithms Based on Weak Factor Recognition ⋮ Worst Case Efficient Single and Multiple String Matching in the RAM Model ⋮ An algorithm to compute the character access count distribution for pattern matching algorithms ⋮ The wide window string matching algorithm ⋮ Unnamed Item ⋮ NR‐grep: a fast and flexible pattern‐matching tool ⋮ A new taxonomy of sublinear right-to-left scanning keyword pattern matching algorithms ⋮ THE DESIGN PRINCIPLES AND ALGORITHMS OF A WEIGHTED GRAMMAR LIBRARY ⋮ A brief history of parameterized matching problems ⋮ Fast string matching for DNA sequences ⋮ A New String Matching Algorithm ⋮ Fast parameterized matching with \(q\)-grams ⋮ A Very Fast String Matching Algorithm Based on Condensed Alphabets ⋮ EFFICIENT VARIANTS OF THE BACKWARD-ORACLE-MATCHING ALGORITHM ⋮ Constant-space string-matching in sublinear average time ⋮ Bit-parallel (\(\delta ,\gamma\))-matching and suffix automata ⋮ A SPACE EFFICIENT BIT-PARALLEL ALGORITHM FOR THE MULTIPLE STRING MATCHING PROBLEM ⋮ Asymptotic estimation of the average number of terminal states in DAWGs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The smallest automaton recognizing the subwords of a text
• Average running time of the Boyer-Moore-Horspool algorithm
• A variation on the Boyer-Moore algorithm
• 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
• The Complexity of Pattern Matching for a Random String
• 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

This page was built for publication: Speeding up two string-matching algorithms