Simple Linear Comparison of Strings in V-order

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

doi:10.3233/FI-2015-1228

Simple Linear Comparison of Strings in V-order

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

Allbwn ymchwil: Cyfraniad at gyfnodolyn › Erthygl › adolygiad gan gymheiriaid

Crynodeb

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.

Iaith wreiddiol	Saesneg
Tudalennau (o-i)	115-126
Nifer y tudalennau	12
Cyfnodolyn	Fundamenta Informaticae
Cyfrol	139
Rhif cyhoeddi	2
Dynodwyr Gwrthrych Digidol (DOIs)	https://doi.org/10.3233/FI-2015-1228
Statws	Cyhoeddwyd - 2015
Cyhoeddwyd yn allanol	Ie

Mynediad at Ddogfen

10.3233/FI-2015-1228

Cysylltiad parhaol

Dolen barhaus

Jacqueline Daykin
- jwd6aber.acuk
- Cyfadran Busnes a’r Gwyddorau Ffisegol, Cyfrifiadureg - Honorary Research Fellow
Unigolyn: Arall

Dyfynnu hyn

@article{8cd5b139f6bb44f4ad08182ba604b717,

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

author = "Ali Alatabbi and Daykin, {Jacqueline W.} and Rahman, {Mohammad Sohel} and Smyth, {William F.}",

year = "2015",

doi = "10.3233/FI-2015-1228",

language = "English",

volume = "139",

pages = "115--126",

journal = "Fundamenta Informaticae",

issn = "0169-2968",

publisher = "IOS Press",

number = "2",

}

TY - JOUR

T1 - Simple Linear Comparison of Strings in V-order

AU - Alatabbi, Ali

AU - Daykin, Jacqueline W.

AU - Rahman, Mohammad Sohel

AU - Smyth, William F.

PY - 2015

Y1 - 2015

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 - V -order

KW - Lyndon word

KW - string

KW - total order

KW - word

U2 - 10.3233/FI-2015-1228

DO - 10.3233/FI-2015-1228

M3 - Article

SN - 0169-2968

VL - 139

SP - 115

EP - 126

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

IS - 2

ER -

Simple Linear Comparison of Strings in V-order

Crynodeb

Mynediad at Ddogfen

Cysylltiad parhaol

Ôl bys

Proffiliau

Jacqueline Daykin

Dyfynnu hyn