Optimal suffix sorting and LCP array construction for constant alphabets

DOI10.1016/J.IPL.2016.09.010zbMATH Open1393.68046OpenAlexW2522274631MaRDI QIDQ344531FDOQ344531

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

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

zbMATH Keywords

data structureslinear timeconstant spaceLCP arraysuffix array

Mathematics Subject Classification ID

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

Cites Work

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

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)