City Research Online

Maximal Closed Substrings

Badkobeh, G. ORCID: 0000-0001-5550-7149, De Luca, A., Fici, G. & Puglisi, S. J. (2022). Maximal Closed Substrings. In: Arroyuelo, D. & Poblete, B. (Eds.), SPIRE 2022: String Processing and Information Retrieval. 29th International Symposium, SPIRE 2022, 8-10 Nov 2022, Concepción, Chile. doi: 10.1007/978-3-031-20643-6_2


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(nlog n+ m) time.

Publication Type: Conference or Workshop Item (Paper)
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
Subjects: Q Science > QA Mathematics
Departments: School of Science & Technology > Computer Science
[thumbnail of Maximal_Closed_Substrings.pdf]
Text - Accepted Version
Download (473kB) | Preview


Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email


Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login