2013/10/12 by Antoine Deza, František Franěk, Deza, Antoine +3
Computer Science · #Algorithms and Data Compression #semigroups and automata theory #Coding theory and cryptography
paper · pdf · doi:10.48550/arxiv.1310.3429
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 5n/3 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 2n/3 double squares. In addition, the established structural properties provide a novel proof of Fraenkel and Simpson's result.