Maximal Closed Substrings

Badkobeh, Golnaz; De Luca, Alessandro; Fici, Gabriele and Puglisi, Simon J.. 2022. Maximal Closed Substrings. Lecture Notes in Computer Science, 13617, pp. 16-23. ISSN 0302-9743 [Article]

Maximal_Closed_Substrings.pdf - Accepted Version

Download (442kB) | Preview

Abstract or Description

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 O(n1.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 O(nlogn+m) time.

Item Type:


Identification Number (DOI):

Additional Information:

“This version of the contribution has been accepted for publication, after peer review (when applicable) but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: Use of this Accepted Version is subject to the publisher’s Accepted Manuscript terms of use”.


Closed Word, Maximal Closed Substring, Run

Departments, Centres and Research Units:

Computing > Goldsmiths Digital Studios


20 August 2022Accepted
1 November 2022Published

Item ID:


Date Deposited:

19 Dec 2022 11:31

Last Modified:

01 Nov 2023 02:42

Peer Reviewed:

Yes, this version has been peer-reviewed.


View statistics for this item...

Edit Record Edit Record (login required)