Efficient Algorithms to Compute Closed Substrings

Abstract

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 fast $\mathcal{O}(n\log n)$ time algorithms to compute all $\mathcal{O}(n^2)$ closed substrings by introducing a compact representation for all closed substrings of a string $w[\mathrm{1..}n]$, using only $\mathcal{O}(n\log n)$ space. These simple and space-efficient algorithms also compute maximal closed strings. Furthermore, we compare the performance of these algorithms and identify classes of strings where each performs best. 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}{\ddot{I}{•}^2}\right)F_n\approx 1.382F_n$, where $\ddot{I}•$ is the golden ratio.

Submitted to TOCS 2026