Name
Abstract | ||
|---|---|---|
We revisit the so-called "Three Squares Lemma" by Crochemore and Rytter [Algorithmica 1995] and, using arguments based on Lyndon words, derive a more general variant which considers three overlapping squares which do not necessarily share a common prefix. We also give an improved upper bound of $n\log_2 n$ on the maximum number of (occurrences of) primitively rooted squares in a string of length $n$, also using arguments based on Lyndon words. To the best of our knowledge, the only known upper bound was $n \log_\phi n \approx 1.441n\log_2 n$, where $\phi$ is the golden ratio, mentioned by Fraenkel and Simpson [TCS 1999] based on a theorem by Crochemore and Rytter [Algorithmica 1995] obtained via the Three Squares Lemma. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/978-3-030-59212-7_19 | SPIRE |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hideo Bannai | 1 | 620 | 79.87 |
| Takuya Mieno | 2 | 0 | 1.01 |
| Yuto Nakashima | 3 | 57 | 19.52 |