TY - GEN
T1 - Efficiently finding all maximal α-gapped repeats
AU - Gawrychowski, Paweł
AU - I, Tomohiro
AU - Inenaga, Shunsuke
AU - Köppl, Dominik
AU - Manea, Florin
N1 - Publisher Copyright:
© Paweł Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl, and Florin Manea; licensed under Creative Commons License CC-BY.
PY - 2016/2/1
Y1 - 2016/2/1
N2 - For α ≥ 1, an α-gapped repeat in a word w is a factor uvu of w such that |uv| ≤ α|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 α-gapped repeats occurring in words of length n is upper bounded by 18αn, allowing us to construct an algorithm finding all maximal α-gapped repeats of a word on an integer alphabet of size nO(1); in O(αn) time. This result is optimal as there are words that have Θ(αn) maximal α-gapped repeats. Our techniques can be extended to get comparable results in the case of α-gapped palindromes, i.e., factors uvuT with |uv| ≤ α|u|.
AB - For α ≥ 1, an α-gapped repeat in a word w is a factor uvu of w such that |uv| ≤ α|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 α-gapped repeats occurring in words of length n is upper bounded by 18αn, allowing us to construct an algorithm finding all maximal α-gapped repeats of a word on an integer alphabet of size nO(1); in O(αn) time. This result is optimal as there are words that have Θ(αn) maximal α-gapped repeats. Our techniques can be extended to get comparable results in the case of α-gapped palindromes, i.e., factors uvuT with |uv| ≤ α|u|.
UR - http://www.scopus.com/inward/record.url?scp=84961615105&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84961615105&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.STACS.2016.39
DO - 10.4230/LIPIcs.STACS.2016.39
M3 - Conference contribution
AN - SCOPUS:84961615105
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016
A2 - Vollmer, Heribert
A2 - Ollinger, Nicolas
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016
Y2 - 17 February 2016 through 20 February 2016
ER -