Improved Upper Bounds on all Maximal α-gapped Repeats and Palindromes

2018/02/28 by I, Tomohiro, Köppl, Dominik · 1 citation
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.1802.10355

Abstract

We show that the number of all maximal α-gapped repeats and palindromes of a word of length n is at most 3(π²/6 + 5/2) αn and 7 (π² / 6 + 1/2) αn - 5 n - 1, respectively.

Cited by

• Fast Computation of k-Runs, Parameterized Squares, and Other Generalised Squares

Related

• Efficiently Finding All Maximal α-gapped Repeats
• Searching of gapped repeats and subrepetitions in a word
• Palindromic Saturation
• Optimal searching of gapped repeats in a word
• Counting scattered palindromes in a finite word