Back to search

McMaster University

EFFICIENT COMPUTATION OF CLOSED SUBSTRINGS

Abstract

dc:description.abstract

A \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 × 3

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Samkith K Jain. EFFICIENT COMPUTATION OF CLOSED SUBSTRINGS. 2026. https://hdl.handle.net/11375/32683