论文标题
在一个单词中几乎最佳地搜索最大子修复
Almost optimal searching of maximal subrepetitions in a word
论文作者
论文摘要
对于$ 0 <δ<1 $ a $Δ$ -subrepeTition，一个单词是指数小于〜2的因素，但不小于$ 1+δ$（该因子的指数是因子长度的比例与其最小周期的比例）。如果$Δ$ - subrepetition不能将其延伸到左侧或右侧至少一个字母，并保留其最小的时期。在本文中，我们提出了一种算法，用于搜索所有最大$δ$ -Subrepetitions，以$ o（\ frac {n}Δ\ log \ frac {1}Δ）$ time（\ frac {n}Δ\ frac {n}Δ\ frac {n}δ）$ time（此时间下的下限为$ω（$ω））。
For $0<δ<1$ a $δ$-subrepetition in a word is a factor which exponent is less than~2 but is not less than $1+δ$ (the exponent of the factor is the ratio of the factor length to its minimal period). The $δ$-subrepetition is maximal if it cannot be extended to the left or to the right by at least one letter with preserving its minimal period. In the paper we propose an algorithm for searching all maximal $δ$-subrepetitions in a word of length~$n$ in $O(\frac{n}δ\log\frac{1}δ)$ time (the lower bound for this time is $Ω(\frac{n}δ)$).
