Affiliations: [a] Department of Informatics, King’s College London, UK. ali.alatabbi@kcl.ac.uk | [b] Department of Computer Science, Royal Holloway, University of London, UK; Department of Informatics, King’s College London, UK. jackie.daykin@rhul.ac.uk; jackie.daykin@kcl.ac.uk | [c] AlEDA Group, Department of CSE, BUET, Dhaka-1205, Bangladesh. msrahman@cse.buet.ac.bd | [d] Algorithms Research Group, Dept. of Computing & Software, McMaster University, Canada; School of Engineering & Information Technology, Murdoch University, Australia. smyth@mcmaster.ca
Note: [*] Preliminary version appeared in [2].
Note: [†] Address for correspondence: Department of Informatics, King’s College London, UK
Note: [‡] Partially supported by a London Mathematical Society Grant for International Short Visits (Scheme 5). Currently on a Sabbatical Leave from BUET.
Abstract: In this paper we focus on a total (but non-lexicographic) ordering of strings called V-order. We devise a new linear-time algorithm for computing the V-comparison of two finite strings. In comparison with the previous algorithm in the literature, our algorithm is both conceptually simpler, based on recording letter positions in increasing order, and more straightforward to implement, requiring only linked lists.
Keywords: algorithm, array, comparison, complexity, data structure, lexicographic order, linear, linked-list, V-order, Lyndon word, string, total order, word
