|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
Optimal Bounds for Computing α-gapped Repeatsстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Дата последнего поиска статьи во внешних источниках: 4 января 2018 г.
- Авторы: Crochemore M., Kolpakov R., Kucherov G.
- Сборник: Language and Automata Theory and Applications - 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings
- Серия: Lecture Notes in Computer Science
- Том: 9618
- Год издания: 2016
- Место издания: Springer International Publishing
- Первая страница: 245
- Последняя страница: 255
- DOI: 10.1007/978-3-319-30000-9_19
- Аннотация: Following (Kolpakov et al., 2013; Gawrychowski and Manea, 2015), we continue the study of α-gapped repeats in strings, defined as factors uvu with |uv|≤α|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) in (Kolpakov et al., 2013). 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 bound of (Kolpakov et al., 2010) by a lognlogn factor. We also prove an algorithmic time bound O(αn+S) (S is the size of the output) for computing all maximal α-gapped repeats. Our solution, inspired by (Gawrychowski and Manea, 2015), is different from the recently published proof by (Tanimura et al., 2015) of the same bound. Together with our bound on S, this implies an O(αn)-time algorithm for computing all maximal α-gapped repeats.
- Добавил в систему: Колпаков Роман Максимович