Catalog Home Page

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.

Publication 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