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 ′ .