Maximal Closed Substrings

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]

Copy

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
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
Date Deposited	19 Dec 2022 11:31
Last Modified	01 Nov 2023 02:42