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

DOI10.1016/j.dam.2016.07.006zbMath1346.05004OpenAlexW2504721752MaRDI QIDQ323035

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

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

experimentsoptimal algorithmonline algorithmlinear timestring comparison\(V\)-comparison\(V\)-orderlexorder

Mathematics Subject Classification ID

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

Related Items

Reconstructing a string from its Lyndon arrays ⋮ A survey of string orderings and their application to the Burrows-Wheeler transform ⋮ Computation of the suffix array, Burrows-Wheeler transform and FM-index in \(V\)-order

Cites Work

• Unnamed Item
• A linear partitioning algorithm for hybrid Lyndons using \(V\)-order
• Suffix array and Lyndon factorization of a text
• Lyndon-like and V-order factorizations of strings
• A bijective variant of the Burrows-Wheeler transform using \(V\)-order
• Simple Linear Comparison of Strings in V-order*
• 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)
• Space Efficient Linear Time Construction of Suffix Arrays
• Jewels of Stringology
• Simple Linear Comparison of Strings in V-Order
• Free differential calculus. IV: The quotient groups of the lower central series