A faster v-order string comparison algorithm

V -order is a total order on strings that determines an instance of Unique Maximal Factorization Families (UMFFs) [7-10], a generalization of Lyndon words [12]. V -order has also recently been proposed as an alternative to lexicographic order (lexorder) in the computation of suffix arrays and in the suffix-sorting induced by the Burrows-Wheeler Transform (BWT) [11]. The central problem of efficient V -ordering of strings was considered in [2-4, 9, 10], culminating in a remarkably simple, linear time, constant space comparison algorithm [1]. In this paper we improve on this result to achieve significant speed-up in almost all cases of interest.