Almost Optimal Searching of Maximal Subrepetitions in a Word

Roman Kolpakov ()
Additional contact information
Roman Kolpakov: Faculty of Mechanics and Mathematics, Moscow Center for Fundamental and Applied Mathematics, Lomonosov Moscow State University, GSP-1, Leninskie Gory, 119991 Moscow, Russia

Mathematics, 2022, vol. 10, issue 19, 1-27

Abstract: For some fixed δ such that 0 < δ < 1 , a δ -subrepetition in a word is a factor whose exponent is less than 2 but is not less than 1 + δ (the exponent of the factor is the ratio of the factor length to its minimal period). The δ -subrepetition is maximal if it cannot be extended to the left or to the right by at least one letter while preserving its minimal period. In the paper, we propose an algorithm for searching all maximal δ -subrepetitions in a word of length n in O ( n δ log 1 δ ) time (the lower bound for this time is Ω ( n δ ) ). It improves the previous known time complexity bounds for solving this problem.

Keywords: combinatorics on words; combinatorial algorithms; time complexity; repetitions (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/19/3569/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/19/3569/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:19:p:3569-:d:929858

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().