On the number of gapped repeats with arbitrary gap

Abstract

For any functions $f(x)$, $g(x)$ from $\mathbb{N}$ to $\mathbb{R}$ we call repeats $uvu$ such that $g(|u|)\le |v|\le 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$.

17 pages, 2 figures. arXiv admin note: text overlap with arXiv:1309.4055, arXiv:1509.01221