2022/09/01 by Golnaz Badkobeh, Badkobeh, Golnaz, Alessandro De Luca +5 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #RNA and protein synthesis mechanisms
paper · doi:10.48550/arxiv.2209.00271
openalex publication_date 2022/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A string is closed if it has length 1 or has a nonempty border without internal occurrences. In this paper we introduce the definition of a maximal closed substring (MCS), which is an occurrence of a closed substring that cannot be extended to the left nor to the right into a longer closed substring. MCSs with exponent at least 2 are commonly called runs; those with exponent smaller than 2, instead, are particular cases of maximal gapped repeats. We provide an algorithm that, given a string of length n locates all MCSs the string contains in \mathcal O(nlog n) time.