2025/06/06 by Jain, Samkith K, Mhaskar, Neerja
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2506.06452
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 and practical O(nlog n) time algorithm to compute all Θ(n2) closed substrings by introducing a compact representation for all closed substrings of a string w[1..n], using only 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) and the longest common prefix (LCP) array of w[1..n]. Finally, we show that the exact number of MCSs (M(fn)) in a Fibonacci word fn , for n ≥ 5, is ≈ (1 + (1)/(ϕ2)) Fn ≈ 1.382 Fn, where ϕ is the golden ratio.