String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time

DOI10.1007/978-3-642-21458-5_8zbMath1339.68329OpenAlexW138343740MaRDI QIDQ3011844

Jacqueline W. Daykin, W. F. Smyth

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)

Related Items (8)

\(V\)-order: new combinatorial properties \& a simple comparison algorithm ⋮ A linear partitioning algorithm for hybrid Lyndons using \(V\)-order ⋮ String rearrangement inequalities and a total order between primitive words ⋮ Reconstructing a string from its Lyndon arrays ⋮ A survey of string orderings and their application to the Burrows-Wheeler transform ⋮ A bijective variant of the Burrows-Wheeler transform using \(V\)-order ⋮ Generic Algorithms for Factoring Strings ⋮ Computation of the suffix array, Burrows-Wheeler transform and FM-index in \(V\)-order

Uses Software

• STAR

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal algorithms for computing the canonical form of a circular string
• Parallel RAM algorithms for factorizing words
• Periodic musical sequences and Lyndon words
• A note on the Burrows-Wheeler transformation
• Lyndon-like and V-order factorizations of strings
• A bijective variant of the Burrows-Wheeler transform using \(V\)-order
• Factorizing words over an ordered alphabet
• Combinatorics of Unique Maximal Factorization Families (UMFFs)
• PROPERTIES AND CONSTRUCTION OF UNIQUE MAXIMAL FACTORIZATION FAMILIES FOR STRINGS
• Generic Algorithms for Factoring Strings
• Free differential calculus. IV: The quotient groups of the lower central series

This page was built for publication: String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time