74
правки
Изменения
м
→Алгоритм Карккайнена-Сандерса
# Сольем эти суффиксные массивы в один за линейное время.
Получили асимптотическое уравнение <tex> T(n) = T\left(\frac23 dfrac23 n\right) + O(n) </tex>, решением которого также является <tex> T(n) = O(n) </tex> (это видно из того, что сумма геометрической прогрессии с основанием <tex> \frac23 dfrac23 </tex> равна <tex> 3 </tex>).
Аналогично первой версии алгоритма, дополним строку <tex> S </tex> до длины, кратной трем, защитными символами <tex> \$ </tex>.
| [[Файл:Kark_sanders_stage3.png|325px|thumb| Фаза 3]]
|}
== Получение массива LCP ==
Массив LCP можно получить за линейное время [[Алгоритм_Касаи_и_др. | алгоритмом Касаи]].
