String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time

David E. Daykin; Jacqueline W. Daykin; W. F. Smyth

doi:10.1007/978-3-642-21458-5_8

String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time

David E. Daykin, Jacqueline W. Daykin, W. F. Smyth

Research output: Chapter in Book/Report/Conference proceeding › Conference Proceeding (Non-Journal item)

Abstract

In this paper we extend previous work on Unique Maximal Factorization Families (UMFFs) and a total (but non-lexicographic) ordering of strings called V-order. We describe linear-time algorithms for string comparison and Lyndon factorization based on V-order. We propose extensions of these algorithms to other forms of order

Original language	English
Title of host publication	Combinatorial Pattern Matching
Subtitle of host publication	22nd Annual Symposium, CPM 2011, Palermo, Italy, June 27-29, 2011. Proceedings
Editors	Raffaele Giancarlo, Giovanni Manzini
Publisher	Springer Nature
Pages	65-76
ISBN (Electronic)	978-3-642-21458-5
ISBN (Print)	978-3-642-21457-8
DOIs	https://doi.org/10.1007/978-3-642-21458-5_8
Publication status	Published - 2011
Externally published	Yes

Publication series

Name	Combinatorial Pattern Matching
Volume	6661
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/978-3-642-21458-5_8

Permanent link

Persistent link

Cite this

Daykin, D. E., Daykin, J. W., & Smyth, W. F. (2011). String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time. In R. Giancarlo, & G. Manzini (Eds.), Combinatorial Pattern Matching: 22nd Annual Symposium, CPM 2011, Palermo, Italy, June 27-29, 2011. Proceedings (pp. 65-76). [Chapter 8] (Combinatorial Pattern Matching; Vol. 6661). Springer Nature. https://doi.org/10.1007/978-3-642-21458-5_8

@inproceedings{fc8885ca91e74c44b0b307e1f97785e4,

title = "String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time",

abstract = "In this paper we extend previous work on Unique Maximal Factorization Families (UMFFs) and a total (but non-lexicographic) ordering of strings called V-order. We describe linear-time algorithms for string comparison and Lyndon factorization based on V-order. We propose extensions of these algorithms to other forms of order",

author = "Daykin, {David E.} and Daykin, {Jacqueline W.} and Smyth, {W. F.}",

year = "2011",

doi = "10.1007/978-3-642-21458-5_8",

language = "English",

isbn = "978-3-642-21457-8",

series = "Combinatorial Pattern Matching",

publisher = "Springer Nature",

pages = "65--76",

editor = "Raffaele Giancarlo and Giovanni Manzini",

booktitle = "Combinatorial Pattern Matching",

address = "Switzerland",

}

Daykin, DE, Daykin, JW & Smyth, WF 2011, String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time. in R Giancarlo & G Manzini (eds), Combinatorial Pattern Matching: 22nd Annual Symposium, CPM 2011, Palermo, Italy, June 27-29, 2011. Proceedings., Chapter 8, Combinatorial Pattern Matching, vol. 6661, Springer Nature, pp. 65-76. https://doi.org/10.1007/978-3-642-21458-5_8

String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time. / Daykin, David E.; Daykin, Jacqueline W.; Smyth, W. F.

Combinatorial Pattern Matching: 22nd Annual Symposium, CPM 2011, Palermo, Italy, June 27-29, 2011. Proceedings. ed. / Raffaele Giancarlo; Giovanni Manzini. Springer Nature, 2011. p. 65-76 Chapter 8 (Combinatorial Pattern Matching; Vol. 6661).

Research output: Chapter in Book/Report/Conference proceeding › Conference Proceeding (Non-Journal item)

TY - GEN

T1 - String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time

AU - Daykin, David E.

AU - Daykin, Jacqueline W.

AU - Smyth, W. F.

PY - 2011

Y1 - 2011

N2 - In this paper we extend previous work on Unique Maximal Factorization Families (UMFFs) and a total (but non-lexicographic) ordering of strings called V-order. We describe linear-time algorithms for string comparison and Lyndon factorization based on V-order. We propose extensions of these algorithms to other forms of order

AB - In this paper we extend previous work on Unique Maximal Factorization Families (UMFFs) and a total (but non-lexicographic) ordering of strings called V-order. We describe linear-time algorithms for string comparison and Lyndon factorization based on V-order. We propose extensions of these algorithms to other forms of order

U2 - 10.1007/978-3-642-21458-5_8

DO - 10.1007/978-3-642-21458-5_8

M3 - Conference Proceeding (Non-Journal item)

SN - 978-3-642-21457-8

T3 - Combinatorial Pattern Matching

SP - 65

EP - 76

BT - Combinatorial Pattern Matching

A2 - Giancarlo, Raffaele

A2 - Manzini, Giovanni

PB - Springer Nature

ER -

String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time

Abstract

Publication series

Access to Document

Permanent link

Fingerprint

Cite this