2017/08/22 by F. Blanchet-Sadri, S. Osborne
Computer Science · Mathematics · #cs.FL #math.CO
paper · pdf · doi:10.4204/eptcs.252.10
published as EPTCS 252, 2017, pp. 71-85 · In Proceedings AFL 2017, arXiv:1708.06226
arxiv created 2017/08/22 · arxiv updated 2017/08/23
Fraenkel and Simpson showed that the number of distinct squares in a word of length n is bounded from above by 2n, since at most two distinct squares have their rightmost, or last, occurrence begin at each position. Improvements by Ilie to 2n-Θ(log n) and by Deza et al. to 11n/6 rely on the study of combinatorics of FS-double-squares, when the maximum number of two last occurrences of squares begin. In this paper, we first study how to maximize runs of FS-double-squares in the prefix of a word. We show that for a given positive integer m, the minimum length of a word beginning with m FS-double-squares, whose lengths are equal, is 7m+3. We construct such a word and analyze its distinct-square-sequence as well as its distinct-square-density. We then generalize our construction. We also construct words with high distinct-square-densities that approach 5/6.