Simple linear comparison of strings in V-order

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

6 Citations (Scopus)


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
Title of host publicationAlgorithms and Computation
Subtitle of host publication8th International Workshop, WALCOM 2014, Chennai, India, February 13-15, 2014, Proceedings
PublisherSpringer International Publishing
Number of pages10
Volume8344 LNCS
ISBN (Electronic)9783319046570
ISBN (Print)9783319046563
Publication statusPublished - 2014
Event8th International Workshop on Algorithms and Computation, WALCOM 2014 - Chennai, India
Duration: 13 Feb 201415 Feb 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8344 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349


Conference8th International Workshop on Algorithms and Computation, WALCOM 2014


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


Dive into the research topics of 'Simple linear comparison of strings in V-order'. Together they form a unique fingerprint.

Cite this