String comparison and Lyndon-like factorization using V-order in linear time

DOI10.1007/978-3-642-21458-5_8MaRDI QIDQ3011844zbMATH OpenOpenAlexFDO

Authors Jacqueline W. Daykin, W. F. Smyth, David E. Daykin

Publication date 29 June 2011

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-21458-5_8

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• A linear partitioning algorithm for hybrid Lyndons using \(V\)-order
• V-order: new combinatorial properties \& a simple comparison algorithm
• Simple linear comparison of strings in V-order (extended abstract)
• Lyndon-like and V-order factorizations of strings
• Simple linear comparison of strings in V-order

Cites work

• A bijective variant of the Burrows-Wheeler transform using V-order
• A note on the Burrows-Wheeler transformation
• Algorithms for the Lyndon unique maximal factorization
• Combinatorics of unique maximal factorization families (UMFFs)
• Factorizing words over an ordered alphabet
• Free differential calculus. IV: The quotient groups of the lower central series
• Generic Algorithms for Factoring Strings
• scientific article; zbMATH DE number 417855 (Why is no real title available?)
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 1146223 (Why is no real title available?)
• Lyndon-like and V-order factorizations of strings
• Optimal algorithms for computing the canonical form of a circular string
• Parallel RAM algorithms for factorizing words
• Periodic musical sequences and Lyndon words
• PROPERTIES AND CONSTRUCTION OF UNIQUE MAXIMAL FACTORIZATION FAMILIES FOR STRINGS

Cited in

(16)

• Reconstructing a string from its Lyndon arrays
• A survey of string orderings and their application to the Burrows-Wheeler transform
• Lyndon-like and V-order factorizations of strings
• Computation of the suffix array, Burrows-Wheeler transform and FM-index in V-order
• Applications of \(V\)-order: suffix arrays, the Burrows-Wheeler transform \& the FM-index
• A bijective variant of the Burrows-Wheeler transform using V-order
• Simple linear comparison of strings in V-order
• V-order: new combinatorial properties \& a simple comparison algorithm
• Combinatorics of unique maximal factorization families (UMFFs)
• PROPERTIES AND CONSTRUCTION OF UNIQUE MAXIMAL FACTORIZATION FAMILIES FOR STRINGS
• A linear partitioning algorithm for hybrid Lyndons using \(V\)-order
• Generic Algorithms for Factoring Strings
• Analyzing strings with ordered Lyndon-like structures
• Simple linear comparison of strings in V-order (extended abstract)
• String rearrangement inequalities and a total order between primitive words
• \(V\)-words, Lyndon words and substring circ-UMFFs

Describes a project that uses

Uses Software

• STAR

This page was built for publication: String comparison and Lyndon-like factorization using V-order in linear time

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