How many double squares can a string contain?

被引：29

作者：

Deza, Antoine ^{[1
,2
]}

Franek, Frantisek ^{[1
]}

Thierry, Adrien ^{[1
]}

机构：

[1] McMaster Univ, Dept Comp & Software, Adv Optimizat Lab, Hamilton, ON, Canada

[2] Univ Paris 11, CNRS, LRI, F-91405 Orsay, France

来源：

DISCRETE APPLIED MATHEMATICS | 2015年 / 180卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

String; Square; Primitively rooted square; Number of distinct squares; Double square; Balanced double square; Factorizable double square; FS-double square; MAXIMUM NUMBER; WORD;

D O I：

10.1016/j.dam.2014.08.016

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 2n distinct squares. Ilie presented in 2007 an asymptotic upper bound of 2n - Theta(log n). We show that a string of length n contains at most [11n/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 [5n/6] particular double squares. In addition, the established structural properties provide a novel proof of Fraenkel and Simpson's result. (C) 2014 Elsevier B.V. All rights reserved.

引用

页码：52 / 69

页数：18

共 11 条

[1] SQUARES, CUBES, AND TIME-SPACE EFFICIENT STRING SEARCHING [J].