How many double squares can a string contain?
| Autor: | Deza, Antoine, Franek, Frantisek, Thierry, Adrien |
|---|---|
| Rok vydání: | 2013 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 29 pages, 20 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|