On the number of gapped repeats with arbitrary gap (Q1708025): Difference between revisions

Let \(w=w[1]w[2]\ldots w[n]\) be an arbitrary word. Consider two functions \(f(x)\), \(g(x)\) from \(\mathbb{N}\) to \(\mathbb{R}^+\) such that \(f(x)\geq g(x)\) for all \(x\in\mathbb{N}\). A subword \(w[i..j]\) is called an \(f,g\)-gapped repeat if it can be represented as \(uvu\) with \(g(|u|)\leq |v|\leq f(|u|)\). An \(f,g\)-gapped repeat \(w[i..j]\) is called a maximal \(f,g\)-gapped repeat if \(w[i-1..j]\) and \(w[i..j+1]\) are not \(f,g\)-gapped repeats. Denote \[ |x|^+=\begin{cases} x,& x>0 \\ 0, & x\leq 0 \end{cases},\qquad |x|^-=\begin{cases} -x,& x<0 \\ 0, & x\geq 0 \end{cases}. \] For any function \(h:\mathbb{N}\to\mathbb{R}^+\) denote \(\partial_h^+=\sup_x |h(x+1)-h(x)|^+\), \(\partial_h^-=\sup_x |h(x+1)-h(x)|^-\). Denote also \(\partial_{f,g}=\min(\max(\partial_f^+,\partial_g^-),\max(\partial_f^-,\partial_g^+))\) and \(\Delta_{f,g}=\sup_x \frac{f(x)-g(x)}{x}\) Suppose that \(\partial_{f,g}\) and \(\Delta_{f,g}\) exist. Then it is proved that a word \(w\) of length \(n\) contains \(O(n(1+\max(\partial_{f,g},\Delta_{f,g})))\) maximal \(f,g\)-gapped repeats.