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 (Scopus)

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

Keywords

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

Fingerprint

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

Cite this