String comparison and Lyndon-like factorization using V-order in linear time

D.E. Daykin; J.W. Daykin; W.F. Smyth

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

Back

String comparison and Lyndon-like factorization using V-order in linear time

Journal article

Peer reviewed

String comparison and Lyndon-like factorization using V-order in linear time

D.E. Daykin, J.W. Daykin and W.F. Smyth

Combinatorial Pattern Matching, Vol.6661, pp.65-76

2011

DOI: https://doi.org/10.1007/978-3-642-21458-5_8

Files and links (1)

url

Link to Published Version *Subscription may be requiredView

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.

Details

Title: String comparison and Lyndon-like factorization using V-order in linear time
Authors/Creators: D.E. Daykin (Author/Creator) - University of Reading
J.W. Daykin (Author/Creator) - University of London
W.F. Smyth (Author/Creator) - McMaster-Carr
Publication Details: Combinatorial Pattern Matching, Vol.6661, pp.65-76
Publisher: Springer Verlag
Identifiers: 991005545249307891
Murdoch Affiliation: Murdoch University
Language: English
Resource Type: Journal article

Metrics

22 Record Views