Cover Image

Construction of Sparse Suffix Trees and LCE Indexes in Optimal Time and Space

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kosolobov, Dmitry, Sivukhin, Nikita
Format:	Preprint
Published:	2021
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Compressed Index with Construction in Compressed Space
by: Kosolobov, Dmitry
Published: (2026)

Simplified Tight Bounds for Monotone Minimal Perfect Hashing
by: Kosolobov, Dmitry
Published: (2024)

Closed Repeats
by: Kosolobov, Dmitry
Published: (2024)

Efficiency of ANS Entropy Encoders
by: Kosolobov, Dmitry
Published: (2022)

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

Dynamic Suffix Array in Optimal Compressed Space
by: Nishimoto, Takaaki, et al.
Published: (2024)

Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
by: Kempa, Dominik, et al.
Published: (2023)

Sparse Suffix and LCP Array: Simple, Direct, Small, and Fast
by: Ayad, Lorraine A. K., et al.
Published: (2023)

Fast and Lightweight Distributed Suffix Array Construction -- First Results
by: Haag, Manuel, et al.
Published: (2024)

Compressing Suffix Trees by Path Decompositions
by: Becker, Ruben, et al.
Published: (2025)

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

Suffix sorting via matching statistics
by: Lipták, Zsuzsanna, et al.
Published: (2022)

Compressing Hypergraphs using Suffix Sorting
by: Adler, Enno, et al.
Published: (2025)

Effective Index Construction Algorithm for Optimal $(k,η)$-cores Computation
by: Sun, Shengli, et al.
Published: (2025)

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

Optimal-Time Move Structure Construction
by: Brown, Nathaniel K., et al.
Published: (2026)

Online and Offline Algorithms for Counting Distinct Closed Factors via Sliding Suffix Trees
by: Mieno, Takuya, et al.
Published: (2024)

Improved Time-Space Tradeoffs for 3SUM-Indexing
by: Dinur, Itai, et al.
Published: (2025)

Time-Optimal Construction of String Synchronizing Sets
by: Ellert, Jonas, et al.
Published: (2026)

Linear Index for Logarithmic Search-Time for any String under any Internal Node in Suffix Trees
by: Al-okaily, Anas
Published: (2024)

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

Gapped String Indexing in Subquadratic Space and Sublinear Query Time
by: Bille, Philip, et al.
Published: (2022)

Suffixient Arrays: a New Efficient Suffix Array Compression Technique
by: Cenzato, Davide, et al.
Published: (2024)

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

Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
by: Kempa, Dominik, et al.
Published: (2025)

Space-Efficient k-Mismatch Text Indexes
by: Kociumaka, Tomasz, et al.
Published: (2025)

Indexing Tries within Entropy-Bounded Space
by: Carfagna, Lorenzo, et al.
Published: (2025)

Enumerating All Directed Spanning Trees in Optimal Time
by: Gawrychowski, Paweł, et al.
Published: (2026)

Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes
by: Mallek, Nadym, et al.
Published: (2025)

Space-Efficient Text Indexing with Mismatches using Function Inversion
by: Bibbens, Jackson, et al.
Published: (2026)

In-Place BWT and Lyndon Array Construction in Constant Space
by: Louza, Felipe A., et al.
Published: (2025)

Space-Efficient Indexes for Uncertain Strings
by: Gabory, Esteban, et al.
Published: (2024)

Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications
by: De Marco, Gianluca, et al.
Published: (2025)

Time, Message and Memory-Optimal Distributed Minimum Spanning Tree and Partwise Aggregation
by: Goldenfeld, Michael Elkin Tanya
Published: (2026)

A Practical Linear Time Algorithm for Optimal Tree Decomposition of Halin Graphs
by: Alejandro-Soto, J. A., et al.
Published: (2025)

Time-Optimal $k$-Server
by: Frei, Fabian, et al.
Published: (2025)

NP-Completeness for the Space-Optimality of Double-Array Tries
by: Bannai, Hideo, et al.
Published: (2024)

Optimal Pure Differentially Private Sparse Histograms in Deterministic Linear Time
by: Kerschbaum, Florian, et al.
Published: (2025)

Multi-Way Co-Ranking: Index-Space Partitioning of Sorted Sequences Without Merge
by: Joshi, Amit
Published: (2025)

Time-Optimal Directed q-Analysis
by: Windisch, Felix, et al.
Published: (2025)