Finding maximal closed substrings
Badkobeh, G. 
ORCID: 0000-0001-5550-7149, De Luca, A., Fici, G. & Puglisi, S. J. (2026).
Finding maximal closed substrings.
Theoretical Computer Science, 1060,
article number 115628.
doi: 10.1016/j.tcs.2025.115628
Abstract
A string is closed if it has length 1 or has a nonempty border without internal occurrences. In this paper, we introduce the notion 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 by one character 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 O(nlogn) time.
| Publication Type: | Article |
|---|---|
| Additional Information: | © 2026. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc-nd/4.0/ |
| Publisher Keywords: | Closed string, Maximal repetition, Gapped repeat, Combinatorial algorithms, Combinatorics on |
| Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science |
| Departments: | School of Science & Technology School of Science & Technology > Department of Computer Science |
| SWORD Depositor: |
![[thumbnail of Maximal_Closed_Substring__Revision_for_TCS_.pdf]](https://openaccess.city.ac.uk/style/images/fileicons/text.png "Maximal_Closed_Substring__Revision_for_TCS_.pdf")
Text
- Accepted Version
This document is not freely accessible until 9 November 2026 due to copyright restrictions.
Available under License Creative Commons Attribution Non-commercial No Derivatives.
To request a copy, please use the button below.
Request a copyExport
Downloads
Downloads per month over past year
Metadata
MetadataActions (login required)
Admin Login