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.
*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|
|Copyright:||© 2012 Elsevier B.V.|
|Item Control Page|