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) (Daykin and Daykin, JDA 2003, and others), a generalization of Lyndon words. 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). The central problem of efficient V-ordering of strings was considered in (Daykin, Daykin and Smyth, TCS 2013, and others), culminating in a remarkably simple, linear time, constant space comparison algorithm (Alatabbi, Daykin, Kärkkäinen, Rahman and Smyth, DAM 2016). In this paper we improve on this result to achieve significant speed-up in almost all cases of interest