Maximal Closed Substrings Golnaz Badkobeh, Alessandro De Luca, Gabriele Fici & Simon J. Puglisi Conference paper First Online: 01 November 2022 243 Accesses Part of the Lecture Notes in Computer Science book series (LNCS,volume 13617) 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 (𝑛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 (𝑛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
Maximal Closed Substrings Golnaz Badkobeh, Alessandro De Luca, Gabriele Fici & Simon J. Puglisi Conference paper First Online: 01 November 2022 243 Accesses Part of the Lecture Notes in Computer Science book series (LNCS,volume 13617) 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 (𝑛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 (𝑛log𝑛+𝑚) time.
| File | Dimensione | Formato | |
|---|---|---|---|
|
Maximal Closed Substrings.pdf
accesso aperto
Tipologia:
Versione Editoriale
Dimensione
286.96 kB
Formato
Adobe PDF
|
286.96 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
