Catalog Home Page

A linear partitioning algorithm for Hybrid Lyndons using -order

Daykin, D.E., Daykin, J.W. and Smyth, W.F. (2013) A linear partitioning algorithm for Hybrid Lyndons using -order. Theoretical Computer Science, 483 . pp. 149-161.

Link to Published Version:
*Subscription may be required


In this paper we extend previous work on unique maximal factorization families (UMFFs) and a total (but non-lexicographic) ordering of strings called VV-order. We present new combinatorial results for VV-order, in particular concatenation under VV-order. We propose linear-time RAM algorithms for string comparison in VV-order and for Lyndon-like factorization of a string into VV-words. This asymptotic efficiency thus matches that of the corresponding algorithms for lexicographical order. Finally, we introduce Hybrid Lyndon words as a generalization of standard Lyndon words, and hence propose extensions of factorization algorithms to other forms of order.

Publication Type: Journal Article
Publisher: Elsevier BV
Copyright: © 2012 Elsevier B.V.
Item Control Page Item Control Page