How many double squares can a string contain?
How many double squares can a string contain?
复制标题
一个字符串可以包含多少个双正方形？
DOI：
10.1016/j.dam.2014.08.016
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
A. Thierry
中科院分区：
文献类型：
--
作者：
A. Deza;F. Franek;A. Thierry
计算正方形的类型，而不是它们的出现，我们考虑的问题的边界的数目不同的正方形在一个字符串。Fraenkel和Simpson在1998年证明了一个长度为n的字符串最多包含2n个不同的正方形。Ilie在2007年提出了一个渐近上界为2 n− Θ（log n）。我们证明了一个长度为n的字符串最多包含<$11 n/6 <$11个不同的正方形。这个新的上界是通过研究双平方的组合结构得到的，并证明了一个长度为n的字符串最多包含<$5n/6 n个特殊的双平方。此外，所建立的结构性质为Fraenkel和Simpson的结果提供了新的证明。
Counting the types of squares rather than their occurrences, we consider the problem of bounding the number of distinct squares in a string. Fraenkel and Simpson showed in 1998 that a string of length n contains at most 2 n distinct squares. Ilie presented in 2007 an asymptotic upper bound of 2 n− Θ (log n). We show that a string of length n contains at most⌊ 11 n/6⌋ distinct squares. This new upper bound is obtained by investigating the combinatorial structure of double squares and showing that a string of length n contains at most⌊ 5 n/6⌋ particular double squares. In addition, the established structural properties provide a novel proof of Fraenkel and Simpson’s result.