74
правки
Изменения
Нет описания правки
* В данном конспекте используется 0-индексация.
* <tex>S[i..j] </tex> — подстрока строки <tex> S </tex> с <tex>i</tex>-го по <tex>j</tex>-й символы включительно.
* Пусть длина строки <tex> S </tex> равна <tex> n </tex>. Обозначим <tex> S[i..j] </tex>, где <tex> j \ge geqslant n </tex> как строку <tex> S[i..n-1] </tex>, дополненную защитными символами <tex> \$ </tex> до длины <tex> n </tex>.
== Алгоритм «разделяй и властвуй» ==
#* Перекодируем строку <tex> S[1..n]S[2..n+1] </tex> в строку <tex> S' </tex> длиной <tex> \frac23 n </tex> в алфавите <tex> \Sigma' </tex>. Тогда суффиксу <tex> S[i..n-1] </tex> в старом алфавите, где <tex> i \bmod 3 = 1 </tex>, в новом алфавите будет соответствовать строка <tex> S'[\frac{i-1}{3}..\frac{n}{3} - 1] </tex>, а если <tex> i\bmod 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 = 3A_{S'}[i] + 1 </tex> в строке <tex> S </tex>, если же <tex> A_{S'}[i] \ge geqslant \frac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j = 3(A_{S'}[i] - \frac{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:
