322
правки
Изменения
м
→Алгоритм Карккайнена-Сандерса
== Алгоритм Карккайнена-Сандерса ==
Изменим изначальный алгоритм следующим образом:
# Построим суффиксный массив для суффиксов, соответствующих позициям, не кратным трем позициям. Рекурсивно сведем это к построению суффиксного массива для строки длиной в две трети исходной.# Построим суффиксный массив для суффиксов, соответствующих кратным трем позициям, используя результат первого шага , за линейное время.# Сливаем Сольем эти суффиксные массивы в один за линейное время.
Получили асимптотическое уравнение <tex> T(n) = T(\frac23 n) + O(n) </tex>, решением которого также является <tex> T(n) = O(n) </tex> (это видно из того, что сумма геометрической прогрессии с основанием <tex> \frac23 </tex> равна <tex> 3n </tex>).
