Lyndon Words, the Three Squares Lemma, and Primitive Squares

Hideo Bannai, Takuya Mieno, Yuto Nakashima

研究成果: 書籍/レポート タイプへの寄稿会議への寄与

抄録

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 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, where is the golden ratio, reported by Fraenkel and Simpson [TCS 1999] obtained via the Three Squares Lemma.

本文言語英語
ホスト出版物のタイトルString Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Proceedings
編集者Christina Boucher, Sharma V. Thankachan
出版社Springer Science and Business Media Deutschland GmbH
ページ265-273
ページ数9
ISBN(印刷版)9783030592110
DOI
出版ステータス出版済み - 2020
イベント27th International Symposium on String Processing and Information Retrieval, SPIRE 2020 - Orlando, 米国
継続期間: 10月 13 202010月 15 2020

出版物シリーズ

名前Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
12303 LNCS
ISSN(印刷版)0302-9743
ISSN(電子版)1611-3349

会議

会議27th International Symposium on String Processing and Information Retrieval, SPIRE 2020
国/地域米国
CityOrlando
Period10/13/2010/15/20

!!!All Science Journal Classification (ASJC) codes

  • 理論的コンピュータサイエンス
  • コンピュータサイエンス一般

フィンガープリント

「Lyndon Words, the Three Squares Lemma, and Primitive Squares」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル