Maximal closed substrings

DOI10.1007/978-3-031-20643-6_2zbMATH Open1525.68201arXiv2209.00271OpenAlexW4312833556MaRDI QIDQ6166967FDOQ6166967

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)

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.

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

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

zbMATH Keywords

runclosed wordmaximal closed substring

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites Work

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

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)