Maximal Closed Substrings

Tools

Badkobeh, Golnaz; De Luca, Alessandro; Fici, Gabriele and Puglisi, Simon J.. 2022. Maximal Closed Substrings. Lecture Notes in Computer Science, 13617, pp. 16-23. ISSN 0302-9743 [Article]

Preview

Text
Maximal_Closed_Substrings.pdf - Accepted Version
Download (442kB) | Preview

Official URL: https://link.springer.com/chapter/10.1007/978-3-03...

Abstract or Description

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(nlogn+m) time.

Item Type:

Article

Identification Number (DOI):

https://doi.org/10.1007/978-3-031-20643-6_2

Additional Information:

“This version of the contribution has been accepted for publication, after peer review (when applicable) but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/978-3-031-20643-6_2. Use of this Accepted Version is subject to the publisher’s Accepted Manuscript terms of use https://www.springernature.com/gp/open-research/policies/accepted-manuscript-terms”.

Keywords:

Closed Word, Maximal Closed Substring, Run

Departments, Centres and Research Units:

Computing
Computing > Goldsmiths Digital Studios

Dates: