文章基本信息

标题：Repetitions in Strings: A "Constant" Problem (Invited Talk)
本地全文：下载
作者：Bannai, Hideo
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：191
页码：1:1-1:1
DOI：10.4230/LIPIcs.CPM.2021.1
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Repeating structures in strings is one of the most fundamental characteristics of strings, and has been an important topic in the field of combinatorics on words and combinatorial pattern matching since their beginnings. In this talk, I will focus on squares and maximal repetitions and review the "runs" theorem [Hideo Bannai et al., 2017] as well as related results (e.g. [Aviezri S. Fraenkel and Jamie Simpson, 1998; Yuta Fujishige et al., 2017; Ryo Sugahara et al., 2019; Philip Bille et al., 2020; Hideo Bannai et al., 2020; Jonas Ellert and Johannes Fischer, 2021]) which address the two main questions: how many of them can be contained in a string of given length, and algorithms for computing them.
关键词：Maximal repetitions; Squares; Lyndon words