Longest common prefix arrays for succinct k-spectra

DOI10.1007/978-3-031-43980-3_1MaRDI QIDQ6545406zbMATH OpenFDO

Authors Jarno N. Alanko, Elena Biagi, Simon J. Puglisi

Publication date 29 May 2024

Full work available at URL https://doi.org/10.1007/978-3-031-43980-3_1

zbMATH Keywords

\(k\)-merBurrows-Wheeler transformBWTcompressed data structuresde Bruijn graphLCPlongest common prefixlongest common suffixstring algorithms

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32) Analysis of algorithms (68W40)

Recommendations

• Space-efficient computation of the LCP array from the Burrows-Wheeler transform
• Algorithm Theory - SWAT 2004
• Space-Time Tradeoffs for Longest-Common-Prefix Array Computation
• Low space external memory construction of the succinct permuted longest common prefix array

Cites work

• Computing the longest common prefix array based on the Burrows-Wheeler transform

Cited in

(2)

• Computing the LCP array of a labeled graph
• On strings having the same length-k substrings

This page was built for publication: Longest common prefix arrays for succinct \(k\)-spectra

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