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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Efficient Computation of Closed Substrings

  • Samkith K. Jain,
  • Neerja Mhaskar

摘要

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.