Maximal Closed Substrings

Abstract

Maximal Closed Substrings Golnaz Badkobeh, Alessandro De Luca, Gabriele Fici & Simon J. Puglisi Conference paper First Online: 01 November 2022 243 Accesses Part of the Lecture Notes in Computer Science book series (LNCS,volume 13617) Abstract 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 show that a string of length n contains (𝑛1.5) MCSs. We also provide an output-sensitive algorithm that, given a string of length n over a constant-size alphabet, locates all m MCSs the string contains in (𝑛log𝑛+𝑚) time.