Speeding up two string-matching algorithms
From MaRDI portal
Publication:1336956
DOI10.1007/BF01185427zbMath0942.68574WikidataQ60163036 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
68Q25: Analysis of algorithms and problem complexity
68R05: Combinatorics in computer science
68W10: Parallel algorithms in computer science
68P20: Information storage and retrieval of data
68U15: Computing methodologies for text processing; mathematical typography
Related Items
A New String Matching Algorithm, Linear and Efficient String Matching Algorithms Based on Weak Factor Recognition, A Bit-Parallel Exact String Matching Algorithm for Small Alphabet, Fast Average-Case Pattern Matching on Weighted Sequences, THE DESIGN PRINCIPLES AND ALGORITHMS OF A WEIGHTED GRAMMAR LIBRARY, Tight bounds on the complexity of the Apostolico-Giancarlo algorithm, Fast and flexible packed string matching, String matching with alphabet sampling, Average complexity of backward \(q\)-gram string matching algorithms, Worst-case efficient single and multiple string matching on packed texts in the word-RAM model, Light-based string matching, Accelerating Boyer-Moore searches on binary texts, Efficient parameterized string matching, A unifying look at the Apostolico--Giancarlo string-matching algorithm, Practical and flexible pattern matching over Ziv-Lempel compressed text., A simple fast hybrid pattern-matching algorithm, A new taxonomy of sublinear right-to-left scanning keyword pattern matching algorithms, Fast parameterized matching with \(q\)-grams, Constant-space string-matching in sublinear average time, Asymptotic estimation of the average number of terminal states in DAWGs, Saving comparisons in the Crochemore-Perrin string-matching algorithm, An algorithm to compute the character access count distribution for pattern matching algorithms, The wide window string matching algorithm, Average complexity of exact and approximate multiple string matching, Efficient online string matching based on characters distance text sampling, A brief history of parameterized matching problems, Fast string matching for DNA sequences, Bit-parallel (\(\delta ,\gamma\))-matching and suffix automata, Improved characters distance sampling for online and offline text searching, On-line string matching algorithms: survey and experimental results, NR‐grep: a fast and flexible pattern‐matching tool, A Very Fast String Matching Algorithm Based on Condensed Alphabets, Worst Case Efficient Single and Multiple String Matching in the RAM Model, Unnamed Item, A SPACE EFFICIENT BIT-PARALLEL ALGORITHM FOR THE MULTIPLE STRING MATCHING PROBLEM, Accelerating Boyer Moore Searches on Binary Texts, EFFICIENT VARIANTS OF THE BACKWARD-ORACLE-MATCHING ALGORITHM
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
