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}{\phi^2}\right) F_n \approx 1.382 F_n$, where $ \phi $ is the golden ratio.
From: Samkith K Jain [view email]
[v1]
Fri, 6 Jun 2025 18:17:45 UTC (454 KB)
[v2]
Mon, 22 Sep 2025 13:37:07 UTC (454 KB)
[v3]
Thu, 8 Jan 2026 21:20:42 UTC (2,636 KB)
[v4]
Sat, 5 Sep 2026 14:15:58 UTC (3,298 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。