On the number of gapped repeats with arbitrary gap

2017/01/05 by Roman Kolpakov, Kolpakov, Roman
Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1701.01190

openalex publication_date 2017/01/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For any functions f(x), g(x) from \mathbb N to \mathbb R we call repeats uvu such that g(|u|)≤ |v|≤ f(|u|) as \it f,g-gapped repeats. We study the possible number of f,g-gapped repeats in words of fixed length~n. For quite weak conditions on f(x), g(x) we obtain an upper bound on this number which is linear to~n.

Citations

• The “Runs” Theorem

Related

• Efficiently Finding All Maximal α-gapped Repeats
• Optimal searching of gapped repeats in a word
• Improved Upper Bounds on all Maximal α-gapped Repeats and Palindromes
• Searching of gapped repeats and subrepetitions in a word
• Envelope Word and Gap Sequence in Doubling Sequence