Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

Simple Linear Comparison of Strings in V-order*

Alatabbi, A., Daykin, J.W., Rahman, M.S. and Smyth, W.F. (2015) Simple Linear Comparison of Strings in V-order*. Fundamenta Informaticae, 139 (2). pp. 115-126.

Link to Published Version:
*Subscription may be required


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.

Item Type: Journal Article
Murdoch Affiliation(s): School of Engineering and Information Technology
Publisher: IOS Press
Item Control Page Item Control Page