Maximal Repetitions in Words or How to Find all Squares in Linear Time
Maximal Repetitions in Words or How to Find all Squares in Linear Time
复制标题
单词中的最大重复次数或如何在线性时间内找到所有平方
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
G. Kucherov
中科院分区：
文献类型：
--
作者：
R. Kolpakov;G. Kucherov
单词$w$中的(分数)重复是周期至多为子字长度的一半的子字。我们研究了出现在$w$中的最大重复次数，即$w$的任何扩展子词都有更大周期的那些。这种重复的集合以紧凑的方式表示$w$中的所有重复。我们首先计算斐波纳契词的最大重复次数。然后，我们证明了我们的主要结果，断言在一般单词中(在任意字母表上)这样的重复的最大次数在长度上是线性的。然后，我们展示了这一结果如何隐含了寻找所有最大重复的线性时间算法。
A (fractional) repetition in a word $w$ is a subword with the period of at most half of the subword length. We study maximal repetitions occurring in $w$, that is those for which any extended subword of $w$ has a bigger period. The set of such repetitions represents in a compact way all repetitions in $w$. We first count the exact number of maximal repetitions in Fibonacci words. Then we prove our main result asserting that the maximal number of such repetitions in general words (on arbitrary alphabet) is linear in the length. We then show how this result implies a linear-time algorithm for finding all maximal repetitions.