Изменения
→Алгоритм skew
Получили асимптотическое уравнение <tex> T(n) = T(\frac23 n) + O(n) </tex>, решением которого также является <tex> T(n) = O(n) </tex> (это видно из того, что сумма геометрической прогрессии с основанием <tex> \frac23 </tex> равна <tex> 3n </tex>).
=== Шаг 1 ===На этом шаге строится суффиксные массивы <tex> A_{S_1} </tex> и <tex> A{TODOS_2} </tex> для множества суффиксов <tex> \{ S[i..n-1] | t i \mod 3 \ne 0 \} </tex>.# Получим строку <tex> S' </tex> аналогично предыдущему алгоритму:#* Сделаем список, состоящий из троек <tex> S[i..i+2]; i \mod 3 \ne 0 </tex>, причем примем <tex> S[n-2..n] = S[n-2..n-1]\$ </tex>, а <tex> S[n-1..n+1] = S[n-1]\$\$ </tex>.#* Отсортируем его за линейное время цифровой сортировкой и получим новый алфавит <tex> \Sigma' </tex>.#* Перекодируем строку <tex> S </tex> в строку <tex> S' </tex> в алфавите <tex> \Sigma' </tex> следущим образом: <tex> S' = [ \Sigma'(s[i..i+2]) | i \mod 3 == 1 ] + [ \Sigma'(s[i..i+2]) | i \mod 3 == 2 ] </tex>. Как можно заметить, длиной строки <tex> S' </tex> будет <tex> n' = \frac23 n </tex>. Суффиксу <tex> S[i..n-1] </tex> в старом алфавите, где <tex> i \mod 3 == 1 </tex>, в новом алфавите будет соответствовать строка <tex> S'[\frac{i-1}{3}..\frac{n}{3} - 1] </tex>, а если <tex> i \mod 3 == 2 </tex>, то строка <tex> S'[\frac{n}{3} + \frac{i-2}{3}..\frac{2n}{3} - 1] </tex>.# Вызовем алгоритм рекурсивно для строки <tex> S' </tex>, получив суффиксный массив <tex> A_{S'} </tex>.# Пройдем по массиву <tex> A_{S'} </tex>. Если <tex> A_{S'}[i] < \frac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j </tex>, где <tex> j \mod 3 = впилить описание сливания = 1 </tex>, тогда добавим в массив <tex> A_{S_1}</tex> значение <tex> 3A_{S'}[i] + 1 </tex>. Если же <tex> A_{S'}[i] \ge \frac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j </tex>, где <tex> j \mod 3 == 2 </tex>, тогда добавим в массив <tex> A_{S_2} </tex> значение <tex> 3(A_{S'}[i] - \frac{n}{3}) + 2 </tex>. Псевдокод этого шага: <tex> A_{S_1} </tex> = [] <tex> A_{S_2} </tex> = [] for i = 0..<tex>A_{S'}</tex>.length: if <tex>A_{S'}</tex>[i] < n / 3: <tex>A_{S_1}</tex>.add(3 * <tex>A_{S'}</tex>[i] + 1) else: <tex>A_{S_2}</tex>.add(3 * (<tex>A_{S'}</tex>[i] - n / 3) + 2)=== Шаг 2 ===ололо
== Ссылки ==
