Simple linear comparison of strings in V-order

Ali Alatabbi; Jackie Daykin; M. Sohel Rahman; William Smythe

doi:10.1007/978-3-319-04657-0_10

Simple linear comparison of strings in V-order

Ali Alatabbi, Jackie Daykin, M. Sohel Rahman, William Smythe

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

6 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 language	English
Title of host publication	Algorithms and Computation
Subtitle of host publication	8th International Workshop, WALCOM 2014, Chennai, India, February 13-15, 2014, Proceedings
Publisher	Springer International Publishing
Pages	80-89
Number of pages	10
Volume	8344 LNCS
ISBN (Electronic)	9783319046570
ISBN (Print)	9783319046563
DOIs	https://doi.org/10.1007/978-3-319-04657-0_10
Publication status	Published - 2014
Event	8th International Workshop on Algorithms and Computation, WALCOM 2014 - Chennai, India Duration: 13 Feb 2014 → 15 Feb 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8344 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	8th International Workshop on Algorithms and Computation, WALCOM 2014
Country/Territory	India
City	Chennai
Period	13/02/2014 → 15/02/2014

Keywords

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

Access to Document

10.1007/978-3-319-04657-0_10

Cite this

Alatabbi, A., Daykin, J., Rahman, M. S., & Smythe, W. (2014). Simple linear comparison of strings in V-order. In Algorithms and Computation: 8th International Workshop, WALCOM 2014, Chennai, India, February 13-15, 2014, Proceedings (Vol. 8344 LNCS, pp. 80-89). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8344 LNCS). Springer International Publishing. https://doi.org/10.1007/978-3-319-04657-0_10

Alatabbi, Ali ; Daykin, Jackie ; Rahman, M. Sohel et al. / Simple linear comparison of strings in V-order. Algorithms and Computation: 8th International Workshop, WALCOM 2014, Chennai, India, February 13-15, 2014, Proceedings. Vol. 8344 LNCS Springer International Publishing, 2014. pp. 80-89 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{9a48d865e6904ea3bfda0e41fdfd4575,

title = "Simple linear comparison of strings in V-order",

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, Lyndon word, string, total order, V-order, word",

author = "Ali Alatabbi and Jackie Daykin and Rahman, {M. Sohel} and William Smythe",

year = "2014",

doi = "10.1007/978-3-319-04657-0_10",

language = "English",

isbn = "9783319046563",

volume = "8344 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer International Publishing",

pages = "80--89",

booktitle = "Algorithms and Computation",

note = "8th International Workshop on Algorithms and Computation, WALCOM 2014 ; Conference date: 13-02-2014 Through 15-02-2014",

}

Alatabbi, A , Daykin, J , Rahman, MS & Smythe, W 2014, Simple linear comparison of strings in V-order. in Algorithms and Computation: 8th International Workshop, WALCOM 2014, Chennai, India, February 13-15, 2014, Proceedings. vol. 8344 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8344 LNCS, Springer International Publishing, pp. 80-89, 8th International Workshop on Algorithms and Computation, WALCOM 2014, Chennai, India, 13/02/2014. https://doi.org/10.1007/978-3-319-04657-0_10

Simple linear comparison of strings in V-order. / Alatabbi, Ali ; Daykin, Jackie ; Rahman, M. Sohel et al.
Algorithms and Computation: 8th International Workshop, WALCOM 2014, Chennai, India, February 13-15, 2014, Proceedings. Vol. 8344 LNCS Springer International Publishing, 2014. p. 80-89 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8344 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

TY - CHAP

T1 - Simple linear comparison of strings in V-order

AU - Alatabbi, Ali

AU - Daykin, Jackie

AU - Rahman, M. Sohel

AU - Smythe, William

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - algorithm

KW - array

KW - comparison

KW - complexity

KW - data structure

KW - lexicographic order

KW - linear

KW - linked-list

KW - Lyndon word

KW - string

KW - total order

KW - V-order

KW - word

U2 - 10.1007/978-3-319-04657-0_10

DO - 10.1007/978-3-319-04657-0_10

M3 - Conference paper

AN - SCOPUS:84958534617

SN - 9783319046563

VL - 8344 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 80

EP - 89

BT - Algorithms and Computation

PB - Springer International Publishing

T2 - 8th International Workshop on Algorithms and Computation, WALCOM 2014

Y2 - 13 February 2014 through 15 February 2014

ER -

Alatabbi A , Daykin J , Rahman MS, Smythe W. Simple linear comparison of strings in V-order. In Algorithms and Computation: 8th International Workshop, WALCOM 2014, Chennai, India, February 13-15, 2014, Proceedings. Vol. 8344 LNCS. Springer International Publishing. 2014. p. 80-89. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-04657-0_10

Simple linear comparison of strings in V-order

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this