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

DOI10.1016/J.JDA.2012.07.007MaRDI QIDQ2376799zbMATH OpenOpenAlexFDO

Authors Timo Beller, Simon Gog, Enno Ohlebusch, Thomas Schnattinger

Publication date 24 June 2013

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2012.07.007

zbMATH Keywords

wavelet treeBurrows-Wheeler transformshortest absent wordslongest common prefix arrayshortest unique substrings

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Combinatorics on words (68R15) Algorithms on strings (68W32)

Recommendations

• Algorithm Theory - SWAT 2004
• Burrows-Wheeler transform and LCP array construction in constant space
• scientific article; zbMATH DE number 1786458
• Computing the BWT and the LCP array in constant space
• Lightweight LCP construction for very large collections of strings

Cited in

(15)

• Permuted Longest-Common-Prefix Array
• Longest common prefix with mismatches
• Sampled Longest Common Prefix Array
• Longest common prefix arrays for succinct \(k\)-spectra
• Space-Time Tradeoffs for Longest-Common-Prefix Array Computation
• Faster lightweight Lempel-Ziv parsing
• Space-efficient computation of the LCP array from the Burrows-Wheeler transform
• Space-efficient construction of compressed suffix trees
• The colored longest common prefix array computed via sequential scans
• Lightweight LCP construction for very large collections of strings
• Edge minimization in de Bruijn graphs
• Burrows-Wheeler transform and LCP array construction in constant space
• LCP array construction in external memory
• Efficient construction of a compressed de Bruijn graph for pan-genome analysis
• Better external memory LCP array construction

This page was built for publication: Computing the longest common prefix array based on the Burrows-Wheeler transform

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