262
правки
Изменения
→Поиск лексикографически минимального суффикса строки
==Поиск лексикографически минимального суффикса строки==
Поиск лексикографически минимального и максимального суффиксов строки - вопрос, который часто поднимается при решении различных теоретических задач. С помощью классического алгоритма Дюваля эта задача решается за линейное время и константный размер дополнительной памяти.
Если заметить, что данная нам строка <tex>S</tex> является подстрокой заранее данного текста <tex>T</tex> длиной <tex>n</tex>, то выполнив некоторый предподсчёт, мы можем получать значения максимального и минимального суффиксов определённой подстроки гораздо быстрее, чем линейно. Это может быть очень полезным при работе с большими объёмами данных (такими как генетический код и т.д.)
Покажем, что <tex>\forall\tau: 1\le\tau\le\log{n}</tex> существует структура данных, размер которой линейно зависит от длины данного текста, со временем запроса <tex>O(\tau)</tex> и временем препроцессинга <tex>O(n\log{n/\tau})</tex> для запросов на нахождение минимального суффикса.
==Ссылки==
