Prague Stringology Conference 2018
Ali Alatabbi, Jacqueline W. Daykin, Mhaskar Neerja, Mohammad Sohel Rahman and William F. Smyth
A Faster V-order String Comparison Algorithm
| Abstract: |
| 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. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |