Maximal closed substrings

DOI10.1007/978-3-031-20643-6_2MaRDI QIDQ6166967zbMATH OpenOpenAlexFDO

Authors Golnaz Badkobeh, Alessandro De Luca, Gabriele Fici, Simon J. Puglisi

Publication date 4 August 2023

Published in String Processing and Information Retrieval (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2209.00271

zbMATH Keywords

runclosed wordmaximal closed substring

Mathematics Subject Classification ID

Algorithms on strings (68W32)

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 $mathcalO(n^{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 $mathcalO(nlogn+m)$ time.

Recommendations

• Closed factorization
• Efficient identification of \(k\)-closed strings
• Off-line and on-line algorithms for closed string factorization
• The number of runs in a string
• Maximal repetitions in strings

Cites work

• scientific article; zbMATH DE number 2185638 (Why is no real title available?)
• A Fast Merging Algorithm
• Enumeration and structure of trapezoidal words
• On the number of closed factors in a word
• Open and closed words
• Periodic-like words, periodicity, and boxes
• Searching of gapped repeats and subrepetitions in a word
• The ``runs theorem
• The sequence of open and closed prefixes of a Sturmian word
• Tighter bounds and optimal algorithms for all maximal -gapped repeats and palindromes. Finding all maximal -gapped repeats and palindromes in optimal worst case time on integer alphabets
• Uniqueness Theorems for Periodic Functions

This page was built for publication: Maximal closed substrings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166967)