Towards optimal packed string matching
From MaRDI portal
Publication:2437754
DOI10.1016/j.tcs.2013.06.013zbMath1282.68184OpenAlexW2046485302MaRDI QIDQ2437754
Oren Ben-Kiki, Roberto Grossi, Oren Weimann, Philip Bille, Leszek Gąsieniec, Dany Breslauer
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
Combinatorics on words (68R15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)
Related Items (3)
Rank and select operations on a word ⋮ Space-efficient Huffman codes revisited ⋮ Fast Convolutions of Packed Strings and Pattern Matching with Wildcards
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Transforming comparison model lower bounds to the parallel-random-access-machine
- Fast searching in packed strings
- Shift-or string matching with super-alphabets
- 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.
- String matching under a general matching relation
- Non-standard stringology
- The exact online string matching problem
- Constant-Time Word-Size String Matching
- Optimal Packed String Matching
- Worst Case Efficient Single and Multiple String Matching in the RAM Model
- Simple Real-Time Constant-Space String Matching
- A fast string searching algorithm
- Approximate String Matching: A Simpler Faster Algorithm
- Deterministic Sampling–A New Technique for Fast Pattern Matching
- Factorizing words over an ordered alphabet
- Parity, circuits, and the polynomial-time hierarchy
- An Optimal $O(\log\log n)$ Time Parallel String Matching Algorithm
- Accelerating Boyer Moore Searches on Binary Texts
- Optimal parallel algorithms for string matching
- Optimal parallel pattern matching in strings
- The Complexity of Pattern Matching for a Random String
- A Lower Bound for Parallel String Matching
- Efficient string matching
- Fast Pattern Matching in Strings
- Algorithms on Strings, Trees and Sequences
- Faster Parallel String Matching via Larger Deterministic Samples
- Two-way string-matching
- A constant-time optimal parallel string-matching algorithm
- Constant-Time Randomized Parallel String Matching
- Trans-dichotomous algorithms without multiplication — some upper and lower bounds
- Uniqueness Theorems for Periodic Functions
This page was built for publication: Towards optimal packed string matching
