2026-08-10T23:00:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5740 2024-03-06T10:36:58Z ddc:004 open_access

Efficiently Finding All Maximal alpha-gapped Repeats Gawrychowski, Pawel I, Tomohiro Inenaga, Shunsuke Köppl, Dominik Manea, Florin combinatorics on words counting algorithms For alpha >=1, an alpha-gapped repeat in a word w is a factor uvu of w such that |uv| <= alpha * |u|; the two occurrences of a factor u in such a repeat are called arms. Such a repeat is called maximal if its arms cannot be extended simultaneously with the same symbol to the right nor to the left. We show that the number of all maximal alpha-gapped repeats occurring in words of length n is upper bounded by 18 * alpha * n, allowing us to construct an algorithm finding all maximal alpha-gapped repeats of a word on an integer alphabet of size n^{O}(1)} in {O}(alpha * n) time. This result is optimal as there are words that have Theta(alpha * n) maximal alpha-gapped repeats. Our techniques can be extended to get comparable results in the case of alpha-gapped palindromes, i.e., factors uvu^{T} with |uv| <= alpha |u|. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pawel Gawrychowski and Tomohiro I and Shunsuke Inenaga and Dominik Köppl and Florin Manea 2016 Is Part Of LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2016.39 urn:nbn:de:0030-drops-57408 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.39 eng https://creativecommons.org/licenses/by/3.0/legalcode