String Comparison in $V$-Order: New Lexicographic Properties & On-line Applications
Ali Alatabbi, Jacqueline W. Daykin, M. Sohel Rahman, W.F. Smyth · arXiv (Cornell University) · 2015
$V$-order is a global order on strings related to Unique Maximal Factorization Families (UMFFs), which are themselves generalizations of Lyndon words. $V$-order has recently been proposed as an alternative to lexicographical order in the computation of suffix arrays and in the suffix-sorting induced by the Burrows-Wheeler transform. Efficient $V$-ordering of strings thus becomes a matter of considerable interest. In this paper we present new and surprising results on $V$-order in strings, then go on to explore the algorithmic consequences.