Cover Image

Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cleary, Alan M., Winjum, Joseph, Dood, Jordan, Inenaga, Shunsuke
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The CDAWG Index and Pattern Matching on Grammar-Compressed Strings
by: Cleary, Alan M., et al.
Published: (2024)

Faster and Simpler Online Computation of String Net Frequency
by: Inenaga, Shunsuke
Published: (2024)

Space-Efficient Online Computation of String Net Occurrences
by: Mieno, Takuya, et al.
Published: (2024)

All-Pairs Suffix-Prefix on Fully Dynamic Set of Strings
by: Kikuchi, Masaru, et al.
Published: (2024)

Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes
by: Duyster, Anouk, et al.
Published: (2026)

Relating Left and Right Extensions of Maximal Repeats
by: Inenaga, Shunsuke, et al.
Published: (2024)

Simple Linear-time Repetition Factorization
by: Yonemoto, Yuki, et al.
Published: (2024)

On the sensitivity of CDAWG-grammars
by: Fujimaru, Hiroto, et al.
Published: (2025)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
by: Fujie, Yuto, et al.
Published: (2025)

Sensitivity of Repetitiveness Measures to String Reversal
by: Bannai, Hideo, et al.
Published: (2026)

On the Number of Non-equivalent Parameterized Squares in a String
by: Hamai, Rikuya, et al.
Published: (2024)

Linear-size Suffix Tries and Linear-size CDAWGs Simplified and Improved
by: Inenaga, Shunsuke
Published: (2024)

Faster and simpler online/sliding rightmost Lempel-Ziv factorizations
by: Sumiyoshi, Wataru, et al.
Published: (2024)

Packed Acyclic Deterministic Finite Automata
by: Shibata, Hiroki, et al.
Published: (2024)

Constant sensitivity on the CDAWGs
by: Hamai, Rikuya, et al.
Published: (2025)

On the number of MUSs crossing a position
by: Fujimaru, Hiroto, et al.
Published: (2025)

Tight bounds for the sensitivity of CDAWGs with left-end edits
by: Fujimaru, Hiroto, et al.
Published: (2023)

Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings
by: De, Rajat, et al.
Published: (2025)

Constant-time edge label and leaf pointer maintenance on sliding suffix trees
by: Leonard, Laurentius, et al.
Published: (2023)

LZBE: an LZ-style compressor supporting $O(\log n)$-time random access
by: Shibata, Hiroki, et al.
Published: (2025)

Faster Space-Efficient STR-IC-LCS Computation
by: Yonemoto, Yuki, et al.
Published: (2022)

Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms
by: Charalampopoulos, Panagiotis, et al.
Published: (2026)

Edit and Alphabet-Ordering Sensitivity of Lex-parse
by: Nakashima, Yuto, et al.
Published: (2024)

Subsequence Matching and LCS with Segment Number Constraints
by: Yonemoto, Yuki, et al.
Published: (2024)

Subsequence Matching and LCS under Cartesian-Tree Equivalence
by: Tsujimoto, Taketo, et al.
Published: (2024)

Counting distinct (non-)crossing substrings
by: Umezaki, Haruki, et al.
Published: (2025)

Computing maximal palindromes in non-standard matching models
by: Mieno, Takuya, et al.
Published: (2022)

String Indexing with Compressed Patterns
by: Bille, Philip, et al.
Published: (2019)

Dynamic Grammar-Compressed Self-Index in $δ$-Optimal Space
by: Nishimoto, Takaaki, et al.
Published: (2026)

Algorithms for Parameterized String Matching with Mismatches
by: Saha, Apurba, et al.
Published: (2024)

Nyldon Factorization of Thue-Morse Words and Fibonacci Words
by: Kishi, Kaisei, et al.
Published: (2025)

Compressed Dictionary Matching on Run-Length Encoded Strings
by: Bille, Philip, et al.
Published: (2025)

Online Computation of Palindromes and Suffix Trees on Tries
by: Shibata, Hiroki, et al.
Published: (2026)

Tight Lower Bounds for Central String Queries in Compressed Space
by: Kempa, Dominik, et al.
Published: (2025)

Revisiting the Sparse Matrix Compression Problem
by: Jugé, Vincent, et al.
Published: (2026)

Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data
by: De, Rajat, et al.
Published: (2023)

Bit catastrophes for the Burrows-Wheeler Transform
by: Giuliani, Sara, et al.
Published: (2024)

Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\sqrt{n}$ Barrier
by: Bodwin, Greg, et al.
Published: (2023)

An Algorithm for the Longest Common Subsequence and Substring Problem for Multiple Strings
by: Li, Rao
Published: (2024)

Counting on General Run-Length Grammars
by: Navarro, Gonzalo, et al.
Published: (2024)