Towards optimal packed string matching
DOI10.1016/J.TCS.2013.06.013zbMATH Open1282.68184OpenAlexW2046485302MaRDI QIDQ2437754FDOQ2437754
Oren Ben-Kiki, Dany Breslauer, Roberto Grossi, Oren Weimann, Philip Bille, Leszek Gąsieniec
Publication date: 13 March 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://orbit.dtu.dk/en/publications/b33e038d-e685-4809-b9e6-53132cd677b4
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Combinatorics on words (68R15) Algorithms on strings (68W32)
Cites Work
- Title not available (Why is that?)
- Two-way string-matching
- Title not available (Why is that?)
- Efficient string matching
- Algorithms on Strings, Trees and Sequences
- Non-standard stringology: algorithms and complexity
- Factorizing words over an ordered alphabet
- Title not available (Why is that?)
- Transforming comparison model lower bounds to the parallel-random-access-machine
- A fast string searching algorithm
- Parity, circuits, and the polynomial-time hierarchy
- Title not available (Why is that?)
- A Lower Bound for Parallel String Matching
- Fast Pattern Matching in Strings
- Title not available (Why is that?)
- Simple Real-Time Constant-Space String Matching
- Title not available (Why is that?)
- Uniqueness Theorems for Periodic Functions
- String matching under a general matching relation
- Approximate String Matching: A Simpler Faster Algorithm
- Deterministic Sampling–A New Technique for Fast Pattern Matching
- Title not available (Why is that?)
- Optimal canonization of all substrings of a string
- Optimal algorithms for computing the canonical form of a circular string
- Parallel RAM algorithms for factorizing words
- On maximal suffixes and constant-space linear-time versions of KMP algorithm.
- The exact online string matching problem: a review of the most recent results
- Optimal packed string matching
- Worst Case Efficient Single and Multiple String Matching in the RAM Model
- The Complexity of Pattern Matching for a Random String
- Fast searching in packed strings
- Shift-or string matching with super-alphabets
- Accelerating Boyer Moore Searches on Binary Texts
- An Optimal $O(\log\log n)$ Time Parallel String Matching Algorithm
- Optimal parallel algorithms for string matching
- Optimal parallel pattern matching in strings
- Title not available (Why is that?)
- Constant-Time Randomized Parallel String Matching
- Title not available (Why is that?)
- A constant-time optimal parallel string-matching algorithm
- Trans-dichotomous algorithms without multiplication — some upper and lower bounds
- Constant-Time Word-Size String Matching
- Faster Parallel String Matching via Larger Deterministic Samples
Cited In (8)
- Fast Packed String Matching for Short Patterns
- Fast Convolutions of Packed Strings and Pattern Matching with Wildcards
- Tighter Packed Bit-Parallel NFA for Approximate String Matching
- Fast and flexible packed string matching
- Rank and select operations on a word
- Space-efficient Huffman codes revisited
- Internal pattern matching queries in a text and applications
- Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing
This page was built for publication: Towards optimal packed string matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437754)
