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> \frac23 dfrac23 n </tex> в алфавите <tex> \Sigma' </tex>. Тогда суффиксу <tex> S[i..n-1] </tex> в старом алфавите, где <tex> i \bmod 3 = 1 </tex>, в новом алфавите будет соответствовать строка <tex> S'[\fracdfrac{i-1}{3}..\fracdfrac{n}{3} - 1] </tex>, а если <tex> i\bmod 3 = 2 </tex>, то строка <tex> S'[\fracdfrac{n}{3} + \fracdfrac{i-2}{3}..\fracdfrac{2n}{3} - 1] </tex>.
# Вызовем алгоритм рекурсивно для строки <tex> S' </tex>, получив суффиксный массив <tex> A_{S'} </tex>.
# Пройдем по массиву <tex> A_{S'} </tex>. Если <tex> A_{S'}[i] < \fracdfrac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j = 3A_{S'}[i] + 1 </tex> в строке <tex> S </tex>, если же <tex> A_{S'}[i] \geqslant \fracdfrac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j = 3(A_{S'}[i] - \fracdfrac{n}{3}) + 2 </tex> в строке <tex> S </tex>. Псевдокод получения <tex> A_{S_{12}} </tex>:
<tex> A_{S_{12}} </tex> = []
'''for''' i = 0..<tex>A_{S'}</tex>.length - 1:
