|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
Optimal bounds for computing alpha-gapped repeatsстатья
- Авторы: Maxime Crochemore, Roman Kolpakov, Gregory Kucherov
- Журнал: Information and Computation
- Том: 268
- Номер: Article 104434
- Год издания: 2019
- Издательство: Academic Press
- Местоположение издательства: United States
- DOI: 10.1016/j.ic.2019.104434
- Аннотация: We continue the study of α-gapped repeats in strings, defined as factors of the form uvu with |uv| =|u| +|v| ≤ α|u|. Our main result is the O(αn)bound on the number of maximal α-gapped repeats in a string of length n, previously proved to be O(α^2n). For a closely related notion of maximal δ-subrepetition (maximal factors of exponent between 1 +δ and 2), our result implies the O(n/δ) bound on their number, which improves the previous bound by a log n factor.We also prove an algorithmic time bound O(αn +S) (S - size of the output) for computing all maximal α-gapped repeats. Together with our bound on S, this implies an O(αn)-time algorithm for computing all maximal α-gapped repeats.
- Добавил в систему: Колпаков Роман Максимович