Optimal suffix sorting and LCP array construction for constant alphabets

DOI10.1016/J.IPL.2016.09.010MaRDI QIDQ344531zbMATH OpenOpenAlexFDO

Authors Felipe A. Louza, Simon Gog, Guilherme P. Telles

Publication date 23 November 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2016.09.010

zbMATH Keywords

data structureslinear timeconstant spaceLCP arraysuffix array

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05) Searching and sorting (68P10)

Recommendations

• Inducing the LCP-array
• LCP array construction in external memory
• LCP array construction using \(O(\operatorname{sort}(n))\) (or less) I/Os
• Permuted Longest-Common-Prefix Array
• Better external memory LCP array construction

Cites work

• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
• Bioinformatics algorithms. Sequence analysis, genome rearrangements, and phylogenetic reconstruction
• Fast and Lightweight LCP-Array Construction Algorithms
• Inducing the LCP-array
• Permuted Longest-Common-Prefix Array
• Space efficient linear time construction of suffix arrays
• Suffix Arrays: A New Method for On-Line String Searches
• Two Efficient Algorithms for Linear Time Suffix Array Construction

Cited in

(7)

• p-suffix sorting as arithmetic coding
• Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays
• Checking Big Suffix and LCP Arrays by Probabilistic Methods
• Burrows-Wheeler transform and LCP array construction in constant space
• Inducing the Lyndon array
• Inducing the LCP-array
• Inducing enhanced suffix arrays for string collections

This page was built for publication: Optimal suffix sorting and LCP array construction for constant alphabets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344531)