Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

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

Daykin, D.E., Daykin, J.W. and Smyth, W.F. (2011) String comparison and Lyndon-like factorization using V-order in linear time. Lecture Notes in Computer Science, 6661 . pp. 65-76.

Link to Published Version: http://dx.doi.org/10.1007/978-3-642-21458-5_8
*Subscription may be required

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.

Item Type: Journal Article
Publisher: Springer Verlag
Copyright: 2011 Springer Berlin Heidelberg
URI: http://researchrepository.murdoch.edu.au/id/eprint/28064
Item Control Page Item Control Page