A linear partitioning algorithm for hybrid Lyndons using \(V\)-order

DOI10.1016/j.tcs.2012.02.001zbMath1292.68130OpenAlexW2080616298MaRDI QIDQ390899

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

Publication date: 9 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.02.001

zbMATH Keywords

lexicographic ordertotal orderstring comparisonconcatenation\(V\)-orderfactorization algorithms\(V\)-wordalphabetcirc-UMFFhybrid Lyndon wordslinear-time RAM algorithmspartitioning algorithmunique maximal factorization family (UMFF)

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Related Items

\(V\)-order: new combinatorial properties \& a simple comparison algorithm, 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
• Unnamed Item
• Unnamed Item
• Computation of words satisfying the ``rhythmic oddity property (after Simha Arom's works)
• 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
• String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time
• 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