Suffix array and Lyndon factorization of a text

DOI10.1016/j.jda.2014.06.001zbMath1306.68127OpenAlexW2007399809MaRDI QIDQ405567

Antonio Restivo, Giovanna Rosone, Sabrina Mantaci, Marinella Sciortino

Publication date: 5 September 2014

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

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

zbMATH Keywords

suffix arrayBWTLyndon wordLyndon factorizationsorting suffixes

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (11)

Extended suffix array construction using Lyndon factors ⋮ \(V\)-order: new combinatorial properties \& a simple comparison algorithm ⋮ Can formal languages help pangenomics to represent and analyze multiple genomes? ⋮ A survey of string orderings and their application to the Burrows-Wheeler transform ⋮ Constructing and indexing the bijective and extended Burrows-Wheeler transform ⋮ Enhanced string factoring from alphabet orderings ⋮ A combinatorial view on string attractors ⋮ On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties ⋮ Cartesian and Lyndon trees ⋮ Inverse Lyndon words and inverse Lyndon factorizations of words ⋮ Computation of the suffix array, Burrows-Wheeler transform and FM-index in \(V\)-order

Cites Work

• Lightweight algorithms for constructing and inverting the BWT of string collections
• A quick tour on suffix arrays and compressed suffix arrays
• A space and time efficient algorithm for constructing compressed suffix arrays
• Parallel RAM algorithms for factorizing words
• Lyndon words, permutations and trees.
• Lightweight data indexing and compression in external memory
• From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization
• An extension of the Burrows-Wheeler transform
• Factorizing words over an ordered alphabet
• Fast parallel Lyndon factorization with applications
• Scalable Parallel Suffix Array Construction
• Words over an ordered alphabet and suffix permutations
• A Constant-Space Comparison-Based Algorithm for Computing the Burrows–Wheeler Transform
• Optimal Dynamic Sequence Representations
• Suffixes, Conjugates and Lyndon Words
• Free differential calculus. IV: The quotient groups of the lower central series
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Suffix array and Lyndon factorization of a text