A gapped repeat is a substring of the form uvu where u is any nonempty string called arm, and v is any string called gap. A gapped repeat is maximal if the characters on the left to both arms differ and those on the right to both arms differ. For any real number \(\alpha \ge 1\) , an \(\alpha \) -gapped repeat is a gapped repeat such that \(|u| + |v| \le \alpha |u|\) . One of the fundamental problems for repetitive structures on strings is analyzing the number of substrings that have such structures in a string. Kolpakov et al. [CPM 2014] showed that \(O(\alpha ^2 n)\) upper bound and \(\varOmega (\alpha n)\) lower bound on the maximum number of maximal \(\alpha \) -gapped repeats in a string of length n, and the current best upper bound is \(3(\pi ^2/6 +5/2)\alpha n\) by I and Köppl [TCS 2019]. Another interesting problem in this line of research is revealing the structures in well-known repetitive strings. In this paper, we investigate the maximal \(\alpha \) -gapped repeats in a Fibonacci string. We show an interesting characterization of the form of an arm. More precisely, there are two possible cases in the form of an arm: Fibonacci arms and palindromic arms. By using these structures, we can obtain an upper bound of the maximum number of maximal \(\alpha \) -gapped repeats in the k-th Fibonacci string. We can also show that the Fibonacci strings are a new example that contains \(\varOmega (\alpha n)\) maximal \(\alpha \) -gapped repeats.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Maximal \(\alpha \) -Gapped Repeats in a Fibonacci String

  • Kazuma Yamane,
  • Yuto Nakashima,
  • Kazuhisa Seto,
  • Takashi Horiyama

摘要

A gapped repeat is a substring of the form uvu where u is any nonempty string called arm, and v is any string called gap. A gapped repeat is maximal if the characters on the left to both arms differ and those on the right to both arms differ. For any real number \(\alpha \ge 1\) , an \(\alpha \) -gapped repeat is a gapped repeat such that \(|u| + |v| \le \alpha |u|\) . One of the fundamental problems for repetitive structures on strings is analyzing the number of substrings that have such structures in a string. Kolpakov et al. [CPM 2014] showed that \(O(\alpha ^2 n)\) upper bound and \(\varOmega (\alpha n)\) lower bound on the maximum number of maximal \(\alpha \) -gapped repeats in a string of length n, and the current best upper bound is \(3(\pi ^2/6 +5/2)\alpha n\) by I and Köppl [TCS 2019]. Another interesting problem in this line of research is revealing the structures in well-known repetitive strings. In this paper, we investigate the maximal \(\alpha \) -gapped repeats in a Fibonacci string. We show an interesting characterization of the form of an arm. More precisely, there are two possible cases in the form of an arm: Fibonacci arms and palindromic arms. By using these structures, we can obtain an upper bound of the maximum number of maximal \(\alpha \) -gapped repeats in the k-th Fibonacci string. We can also show that the Fibonacci strings are a new example that contains \(\varOmega (\alpha n)\) maximal \(\alpha \) -gapped repeats.