Получили асимптотическое уравнение <tex> T(n) = T(\frac23 n) + O(n) </tex>, решением которого также является <tex> T(n) = O(n) </tex> (это видно из того, что сумма геометрической прогрессии с основанием <tex> \frac23 </tex> равна <tex> 3n </tex>).
Аналогично первой версии алгоритма, дополним строку <tex> S </tex> до длины, кратной трем, защитными символами <tex> \$ </tex>.
=== Шаг 1 ===
=== Шаг 2 ===
ололоЭтот шаг также аналогичен первой версии алгоритма. Сортировка множества <tex> \{ S[i..n-1] | i \mod 3 == 0 \} </tex> аналогична сортировке пар <tex> \{ (S[i], S[i+1..n-1]) | i \mod 3 == 0 \} </tex>, где <tex> S[i+1..n-1] </tex> — суффиксы в позициях, равных 1 по модулю 3, относительный порядок которых уже известен. Выпишем эти пары в порядке вхождения их в <tex> A_{S_{12}} </tex> и отсортируем по первому элементу устойчивой сортировкой подсчетом, получив суффиксный массив <tex> A_{S_0} </tex>. Псевдокод этого шага: <tex>A_{S_0}</tex> = [] M = [] for i = 0..2n/3: if <tex> A_{S_{12}}</tex>[i] % 3 == 1: M.add(Pair(S[A_{S_{12}}</tex>[i] - 1], A_{S_{12}}</tex>[i])) stable_sort(M) for i = 0..n/3: <tex>A_{S_0}</tex>.add(M[i].second - 1)Аналогично, второй шаг требует <tex> O(n) </tex> времени.
== Ссылки ==
