V-order: new combinatorial properties \& a simple comparison algorithm

DOI10.1016/J.DAM.2016.07.006MaRDI QIDQ323035zbMATH OpenOpenAlexFDO

Authors Ali Alatabbi, Jacqueline W. Daykin, Juha Kärkkäinen, M. Sohel Rahman, W. F. Smyth

Publication date 7 October 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2016.07.006

zbMATH Keywords

online algorithmexperimentsoptimal algorithmlinear timestring comparison\(V\)-comparison\(V\)-orderlexorder

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Online algorithms; streaming algorithms (68W27) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Recommendations

• Applications of \(V\)-order: suffix arrays, the Burrows-Wheeler transform \& the FM-index
• Computation of the suffix array, Burrows-Wheeler transform and FM-index in \(V\)-order
• Simple linear comparison of strings in \(V\)-order
• String comparison and Lyndon-like factorization using V-order in linear time
• Simple linear comparison of strings in \(V\)-order (extended abstract)

Cites work

• scientific article; zbMATH DE number 1146223 (Why is no real title available?)
• A bijective variant of the Burrows-Wheeler transform using \(V\)-order
• A linear partitioning algorithm for hybrid Lyndons using \(V\)-order
• 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
• Jewels of Stringology
• Lyndon-like and V-order factorizations of strings
• Simple linear comparison of strings in \(V\)-order
• Simple linear comparison of strings in \(V\)-order (extended abstract)
• Space efficient linear time construction of suffix arrays
• String comparison and Lyndon-like factorization using V-order in linear time
• Suffix array and Lyndon factorization of a text

Cited in

(9)

• Computation of the suffix array, Burrows-Wheeler transform and FM-index in \(V\)-order
• Simple linear comparison of strings in \(V\)-order
• A survey of string orderings and their application to the Burrows-Wheeler transform
• Reconstructing a string from its Lyndon arrays
• A linear partitioning algorithm for hybrid Lyndons using \(V\)-order
• \(V\)-words, Lyndon words and substring circ-UMFFs
• String comparison and Lyndon-like factorization using V-order in linear time
• Applications of \(V\)-order: suffix arrays, the Burrows-Wheeler transform \& the FM-index
• Simple linear comparison of strings in \(V\)-order (extended abstract)

This page was built for publication: \(V\)-order: new combinatorial properties \& a simple comparison algorithm

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