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.
Badkobeh, G., De Luca, A., Fici, G., Puglisi, S.J. (2026). Finding maximal closed substrings. THEORETICAL COMPUTER SCIENCE, 1060 [10.1016/j.tcs.2025.115628].
Finding maximal closed substrings
De Luca A.;Fici G.
;
2026-01-18
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.
| File | Dimensione | Formato | |
|---|---|---|---|
|
1-s2.0-S0304397525005663-main (1).pdf
Solo gestori archvio
Tipologia:
Versione Editoriale
Dimensione
1.57 MB
Formato
Adobe PDF
|
1.57 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
