论文标题
Lyndon单词，三个正方形引理和原始正方形
Lyndon Words, the Three Squares Lemma, and Primitive Squares
论文作者
论文摘要
我们重新审视了Crochemore和Rytter [Algorithmica 1995]所谓的“三个正方形引理”，并使用基于lyndon词的参数得出了一个更一般的变体，该变体认为三个不一定共享常见前缀的重叠正方形。我们还提供了$ n \ log_2 n $的改进的上限，以最大的（出现）为基本扎根的正方形的（出现），以$ n $的长度为基础，也使用基于lyndon单词的参数。据我们所知，唯一已知的上限是$ n \ log_ϕn \大约1.441n \ log_2 n $，其中$ ϕ $是黄金比率，由Fraenkel和Simpson [TCS 1999]通过三个正方形凸出获得。
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_ϕn \approx 1.441n\log_2 n$, where $ϕ$ is the golden ratio, reported by Fraenkel and Simpson [TCS 1999] obtained via the Three Squares Lemma.
