Home
Scholarly Works
Efficient Algorithms to Compute Closed Substrings
Preprint

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[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 \geq 5$, is $\approx \left(1 + \frac{1}{ϕ^2}\right) F_n \approx 1.382 F_n$, where $ ϕ$ is the golden ratio.

Authors

Jain SK; Mhaskar N

Publication date

January 8, 2026

DOI

10.48550/arxiv.2506.06452

Preprint server

arXiv

Labels

View published work (Non-McMaster Users)

Contact the Experts team