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