Finding Maximal Repetitions in a Word in Linear Time

Авторы: Kolpakov R., Kucherov G.
Сборник: Proceedings of 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS'99)
Год издания: 1999
Первая страница: 596
Последняя страница: 604
DOI: 10.1109/SFFCS.1999.814634
Аннотация: A repetition in a word w is a sub-word with the period of at most half of the sub-word length. We study maximal repetitions occurring in w, that is those for which any extended sub-word of w has a bigger period. The set of such repetitions represents in a compact way all repetitions in w.We first prove a combinatorial result asserting that the sum of exponents of all maximal repetitions of a word of length n is bounded by a linear function in n. This implies, in particular, that there is only a linear number of maximal repetitions in a word. This allows us to construct a linear-time algorithm for finding all maximal repetitions. Some consequences and applications of these results are discussed, as well as related works.
Добавил в систему: Колпаков Роман Максимович

	ИСТИНА	Войти в систему Регистрация
	Интеллектуальная Система Тематического Исследования НАукометрических данных
	Главная Поиск Статистика О проекте Помощь

ИСТИНА