Computation of the suffix array, Burrows-Wheeler transform and FM-index in \(V\)-order

DOI10.1016/j.tcs.2021.06.004OpenAlexW3169874067MaRDI QIDQ2043023

Jacqueline W. Daykin, W. F. Smyth, Neerja Mhaskar

Publication date: 22 July 2021

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

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

zbMATH Keywords

combinatoricsBurrows-Wheeler transformstring comparison\(V\)-orderlexorderFM-indexsuffix sorting\(V\)-BWTsubstring pattern matching

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

A new class of string transformations for compressed text indexing

Cites Work

• Unnamed Item
• \(V\)-order: new combinatorial properties \& a simple comparison algorithm
• A linear partitioning algorithm for hybrid Lyndons using \(V\)-order
• Suffix array and Lyndon factorization of a text
• Reconstructing a string from its Lyndon arrays
• Lyndon-like and V-order factorizations of strings
• Applications of \(V\)-order: suffix arrays, the Burrows-Wheeler transform \& the FM-index
• 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
• Combinatorics of Unique Maximal Factorization Families (UMFFs)
• Space Efficient Linear Time Construction of Suffix Arrays
• The “Runs” Theorem
• Linear-time Suffix Sorting - A New Approach for Suffix Array Construction.
• Algorithms on Strings
• Simple Linear Comparison of Strings in V-Order
• Free differential calculus. IV: The quotient groups of the lower central series