Conference
A note on the number of squares in a word
Abstract
Fraenkel and Simpson [A.S. Fraenkel, J. Simpson, How many squares can a string contain? J. Combin. Theory Ser. A 82 (1998) 112–120] proved that the number of squares in a word of length n is bounded by 2n. In this note we improve this bound to 2n−Θ(logn). Based on the numerical evidence, the conjectured bound is n.
Authors
Ilie L
Volume
380
Pagination
pp. 373-376
Publisher
Elsevier
Publication Date
June 2007
DOI
10.1016/j.tcs.2007.03.025
Conference proceedings
Theoretical Computer Science
Issue
3
ISSN
0304-3975