Efficient Computation of Closed Substrings
摘要
A closed string u 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 \(\mathcal {O}(n\log n)\) time algorithm to compute all \(\mathcal {O}(n^2)\) closed substrings by introducing a compact representation for all closed substrings of a string w[1..n], using only \(\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 ( \(\textsf{SA}\) ) and the longest common prefix ( \(\textsf{LCP}\) ) array of w[1..n]. Finally, we show that the exact number of MCSs ( \(M(f_n)\) ) in a Fibonacci word \( f_n \) , for \(n \ge 5\) , is \(\approx \left( 1 + \frac{1}{\phi ^2}\right) F_n \approx 1.382 F_n\) , where \( \phi \) is the golden ratio.