Simple linear comparison of strings in V-order

DOI10.3233/FI-2015-1228zbMATH Open1335.68303OpenAlexW1248144726MaRDI QIDQ2805461FDOQ2805461

M. Sohel Rahman, W. F. Smyth, Jacqueline W. Daykin, Ali Alatabbi

Publication date: 11 May 2016

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/fi-2015-1228

Recommendations

• Simple linear comparison of strings in \(V\)-order (extended abstract)
• \(V\)-order: new combinatorial properties \& a simple comparison algorithm
• String comparison and Lyndon-like factorization using V-order in linear time
• A linear partitioning algorithm for hybrid Lyndons using \(V\)-order
• Applications of \(V\)-order: suffix arrays, the Burrows-Wheeler transform \& the FM-index

zbMATH Keywords

Lyndon wordcomplexitydata structurelexicographic order\(V\)-orderarraytotal orderlinked listlinear comparison

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cited In (5)

• Comparing Degenerate Strings
• \(V\)-words, Lyndon words and substring circ-UMFFs
• \(V\)-order: new combinatorial properties \& a simple comparison algorithm
• Computation of the suffix array, Burrows-Wheeler transform and FM-index in \(V\)-order
• A survey of string orderings and their application to the Burrows-Wheeler transform

This page was built for publication: Simple linear comparison of strings in \(V\)-order

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