Extracting the sparse longest common prefix array from the suffix binary search tree

DOI10.1007/978-3-030-86692-1_12OpenAlexW3202020418MaRDI QIDQ2146135

Dominik Köppl, Robert W. Irving, Lorna Love, Tomohiro I.

Publication date: 15 June 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-86692-1_12

zbMATH Keywords

Euler tourlongest common prefixessparse suffix sortingsuffix binary search tree

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05)

Uses Software

• essaMEM

Cites Work

• Unnamed Item
• LCP array construction using \(O(\operatorname{sort}(n))\) (or less) I/Os
• The suffix binary search tree and suffix AVL tree
• Geometric BWT: compressed text indexing via sparse suffixes and range searching
• Faster Sparse Suffix Sorting
• Sparse and Truncated Suffix Trees on Variable-Length Codes
• Suffix Arrays: A New Method for On-Line String Searches
• Suffix Arrays on Words
• Sparse Text Indexing in Small Space
• Locally Consistent Parsing for Text Indexing in Small Space
• Deterministic Sparse Suffix Sorting in the Restore Model
• Sparse suffix trees

This page was built for publication: Extracting the sparse longest common prefix array from the suffix binary search tree