Simple Linear Comparison of Strings in V-order

Ali Alatabbi, Jacqueline W. Daykin, Mohammad Sohel Rahman, William F. Smyth

Research output: Contribution to journalArticlepeer-review

4 Citations (SciVal)


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.
Original languageEnglish
Pages (from-to)115-126
Number of pages12
JournalFundamenta Informaticae
Issue number2
Publication statusPublished - 2015
Externally publishedYes


  • algorithm
  • array
  • comparison
  • complexity
  • data structure
  • lexicographic order
  • linear
  • linked-list
  • V -order
  • Lyndon word
  • string
  • total order
  • word


Dive into the research topics of 'Simple Linear Comparison of Strings in V-order'. Together they form a unique fingerprint.

Cite this