Efficient Algorithms for Longest Closed Factor Array

Abstract

We consider a family of strings called closed strings and a related array of Longest Closed Factors (LCF). We show that the reconstruction of a string from its LCF array is easier than the construction and verification of this array. Moreover, the reconstructed string is unique. We improve also the time of construction/verification, reducing it from $O(n\log n/\log \log n)$ (the best previously known) to $O(n\sqrt{\log n})$. We use connections between the LCF array and the longest previous/next factor arrays.