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 (𝑛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 O (𝑛log𝑛+𝑚) time.
Badkobeh, G., De Luca, A., Fici, G., Puglisi, S.J. (2022). Maximal Closed Substrings. In D. Arroyuelo, B. Poblete (a cura di), String Processing and Information Retrieval. 29th International Symposium, SPIRE 2022 Concepción, Chile, November 8–10, 2022. Proceedings (pp. 16-23) [10.1007/978-3-031-20643-6_2].
Maximal Closed Substrings
Badkobeh G.;De Luca A.;Fici G.
;Puglisi S. J.
2022-01-01
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 O (𝑛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 O (𝑛log𝑛+𝑚) time.
| File | Dimensione | Formato | |
|---|---|---|---|
|
fici.pdf
accesso aperto
Tipologia:
Versione Editoriale
Dimensione
5.2 MB
Formato
Adobe PDF
|
5.2 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
