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.
*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 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|
|Copyright:||2011 Springer Berlin Heidelberg|
|Item Control Page|