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

DOI10.1016/j.jda.2012.07.007zbMath1267.68322OpenAlexW2042175004MaRDI QIDQ2376799

Simon Gog, Enno Ohlebusch, Timo Beller, 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

Burrows-Wheeler transformwavelet treeshortest absent wordslongest common prefix arrayshortest unique substrings

Mathematics Subject Classification ID

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

Related Items (10)

Lightweight LCP construction for very large collections of strings ⋮ Efficient Construction of a Compressed de Bruijn Graph for Pan-Genome Analysis ⋮ Faster Lightweight Lempel-Ziv Parsing ⋮ Edge minimization in de Bruijn graphs ⋮ Longest Common Prefix with Mismatches ⋮ Space-efficient construction of compressed suffix trees ⋮ Better External Memory LCP Array Construction ⋮ Burrows-Wheeler transform and LCP array construction in constant space ⋮ Space-efficient computation of the LCP array from the Burrows-Wheeler transform ⋮ LCP Array Construction in External Memory

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