





















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}δ)$).
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。