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.
Maximal Closed Substrings / Badkobeh, G.; De Luca, A.; Fici, G.; Puglisi, S. J.. - 13617:(2022), pp. 16-23. (Intervento presentato al convegno 29th International Symposium on String Processing and Information Retrieval, SPIRE 2022 tenutosi a Concepción, Chile nel 2022) [10.1007/978-3-031-20643-6_2].
Maximal Closed Substrings
De Luca A.;
2022
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(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.File | Dimensione | Formato | |
---|---|---|---|
2209.00271.pdf
solo utenti autorizzati
Descrizione: arXiv preprint
Tipologia:
Documento in Pre-print
Licenza:
Creative commons
Dimensione
156.08 kB
Formato
Adobe PDF
|
156.08 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.