A Faster V-order String Comparison Algorithm

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

Research output: Contribution to conferencePaperpeer-review

3 Citations (Scopus)


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
Original languageEnglish
Publication statusPublished - 2018
EventPrague Stringology Conference - Czech Technical University, Prague, Czech Republic
Duration: 27 Aug 201828 Aug 2018


ConferencePrague Stringology Conference
Country/TerritoryCzech Republic
Period27 Aug 201828 Aug 2018


Dive into the research topics of 'A Faster V-order String Comparison Algorithm'. Together they form a unique fingerprint.

Cite this