Efficient Computation of Closed Substrings

A closed stringu is either of length one or contains a border that occurs only as a prefix and as a suffix in u and nowhere else within u. In this paper, we present a fast O(nlogn)$$\mathcal {O}(n\log n)$$ time algorithm to compute all O(n2)$$\mathcal {O}(n^2)$$ closed substrings by introducing a compact representation for all closed substrings of a string w[1..n], using only O(nlogn)$$\mathcal {O}(n \log n)$$ space. We also present a simple and space-efficient solution to compute all maximal closed substrings (MCSs) using the suffix array (SA$$\textsf{SA}$$) and the longest common prefix (LCP$$\textsf{LCP}$$) array of w[1..n]. Finally, we show that the exact number of MCSs (M(fn)$$M(f_n)$$) in a Fibonacci word fn$$ f_n $$, for n≥5$$n \ge 5$$, is ≈1+1ϕ2Fn≈1.382Fn$$\approx \left( 1 + \frac{1}{\phi ^2}\right) F_n \approx 1.382 F_n$$, where ϕ$$ \phi $$ is the golden ratio.