Off-line and on-line algorithms for closed string factorization.

A string X = X [ 1.. n ] , n > 1 , is said to be closed if it has a nonempty proper prefix that is also a suffix, but that otherwise occurs nowhere else in X ; for n = 1 , every X is closed. Closed strings were introduced by Fici in [1] as objects of combinatorial interest. Recently Badkobeh et al. [2] described a variety of algorithms to factor a given string into closed factors. In particular, they studied the Longest Closed Factorization (LCF) problem, which greedily computes the decomposition X = X 1 X 2 ⋯ X k , where X 1 is the longest closed prefix of X , X 2 the longest closed prefix of X with prefix X 1 removed, and so on. In this paper we present an O (log ⁡ n) amortized per character algorithm to compute LCF on-line, where n is the length of the string. We also introduce the Minimum Closed Factorization (MCF) problem, which identifies the minimum number of closed factors that cover X. We first describe an off-line O (n log 2 ⁡ n) -time algorithm to compute M C F (X) , then we present an on-line algorithm for the same problem. In fact, we show that M C F (X) can be computed in O (L log ⁡ n) time from M C F (X ′) , where X ′ = X [ 1.. n − 1 ] , and L is the largest integer such that the suffix X [ n − L + 1.. n ] is a substring of X ′. [ABSTRACT FROM AUTHOR]