Reconstructing a string from its Lyndon arrays

DOI10.1016/j.tcs.2017.04.008zbMath1386.68234OpenAlexW2610819251MaRDI QIDQ1698704

Frantisek Franek, Jacqueline W. Daykin, Jan Holub, A. S. M. Sohidull Islam, W. F. Smyth

Publication date: 16 February 2018

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

Full work available at URL: https://researchrepository.murdoch.edu.au/id/eprint/37066/

zbMATH Keywords

reverse engineeringLyndon wordstring reconstructionLyndon arrayLyndon factorisation

Mathematics Subject Classification ID

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

Related Items

Enhanced string factoring from alphabet orderings ⋮ When a dollar makes a BWT ⋮ A new approach to regular \& indeterminate strings ⋮ Computation of the suffix array, Burrows-Wheeler transform and FM-index in \(V\)-order ⋮ On the size of the smallest alphabet for Lyndon trees ⋮ Longest Lyndon Substring After Edit

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(V\)-order: new combinatorial properties \& a simple comparison algorithm
• A linear partitioning algorithm for hybrid Lyndons using \(V\)-order
• Indeterminate strings, prefix arrays \& undirected graphs
• Validating the Knuth-Morris-Pratt failure function, fast and online
• Lyndon-like and V-order factorizations of strings
• Inferring an indeterminate string from a prefix graph
• 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
• Validating the Knuth-Morris-Pratt Failure Function, Fast and Online
• Cover Array String Reconstruction
• Generating Lyndon brackets.
• Generic Algorithms for Factoring Strings
• Linear-time Suffix Sorting - A New Approach for Suffix Array Construction.
• REVERSE ENGINEERING PREFIX TABLES
• Free differential calculus. IV: The quotient groups of the lower central series