74
правки
Изменения
→Шаг 1
#* Сделаем список, состоящий из троек <tex> S[i..i+2]</tex> , где <tex> i \bmod 3 \ne 0 </tex>.
#* Отсортируем его за линейное время цифровой сортировкой и получим новый алфавит <tex> \Sigma' </tex>.
#* Перекодируем строку <tex> S[1..n]S[2..n+1] </tex> в строку <tex> S' </tex> длиной <tex> \dfrac23 n </tex> в алфавите <tex> \Sigma' </tex>. Тогда суффиксу <tex> S[i..n-1] </tex> в старом алфавите, где <tex> i \bmod 3 = 1 </tex>, в новом алфавите будет соответствовать строка <tex> S'\left[\dfrac{i-1}{3}..\dfrac{n}{3} - 1\right] </tex>, а если <tex> i\bmod 3 = 2 </tex>, то строка <tex> S'\left[\dfrac{n}{3} + \dfrac{i-2}{3}..\dfrac{2n}{3} - 1\right] </tex>.
# Вызовем алгоритм рекурсивно для строки <tex> S' </tex>, получив суффиксный массив <tex> A_{S'} </tex>.
# Пройдем по массиву <tex> A_{S'} </tex>. Если <tex> A_{S'}[i] < \dfrac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j = 3A_{S'}[i] + 1 </tex> в строке <tex> S </tex>, если же <tex> A_{S'}[i] \geqslant \dfrac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j = 3\left(A_{S'}[i] - \dfrac{n}{3}\right) + 2 </tex> в строке <tex> S </tex>. Псевдокод получения <tex> A_{S_{12}} </tex>:
<tex> A_{S_{12}} </tex> = []
'''for''' i = 0..'''to''' <tex>A_{S'}</tex>.length - 1:
'''if''' <tex>A_{S'}</tex>[i] < n / 3:
<tex>A_{S_{12}}</tex>.add(3 * <tex>A_{S'}</tex>[i] + 1)
