Abstract
dc:description.abstractA \df{closed string} $ u $ is either of length one or contains a border that occurs only as a prefix and as a suffix of $ u $, without appearing elsewhere within $ u $. This thesis presents a fast and practical $ \mathcal{O}(n \log n) $ time algorithm to compute all \mathcal{O}(n2) closed substrings of a string $ w[1..n] $. This is achieved by introducing a compact representation of all closed substrings using only $ \mathcal{O}(n \log n) $ space. Additionally, a simple and space-efficient approach is proposed to compute all maximal closed substrings (MCSs) using the suffix array ($\mathsf{SA}$) and the longest common prefix ($\mathsf{LCP}$) array of $ w[1..n] $. Given a Fibonacci word fn, where $n>5$, the thesis shows that the exact number of MCSs is M(fn) \approx \left(1 + \frac{1}{\phi2}\right) Fn \approx 1.382 Fn , where $ \phi $ is the golden ratio, and Fn is the $ n $-th Fibonacci number. These results highlight novel combinatorial properties of closed substrings in structured sequences. To complement the theoretical findings, an efficient implementation of the algorithms for computing closed strings and MCSs is provided. The implementation has been thoroughly tested and is designed to support practical applications, facilitating further exploration of closed substrings in various contexts.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Samkith K Jain
Subjects
dc:subject × 3Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Identifier URI
- https://doi.org/10.71548/18342