1679
правок
Изменения
Нет описания правки
# Отобразим исходную строку <tex> S </tex> длины <tex> n </tex> в строку <tex> S' </tex> длины <tex> \frac{n}{2} </tex> следующим образом:
#* Сделаем список, состоящий из пар символов вида <tex> S[i..i + 1] </tex>, где <tex> i \mod bmod 2 = 1 </tex>.
#* Отсортируем его цифровой сортировкой за линейное время и получим новый алфавит <tex> \Sigma' </tex>.
#* Перекодируем строку <tex> S[1..n] </tex> в алфавит <tex> \Sigma' </tex>, получив строку <tex> S' </tex> половинной длины.
На этом шаге мы за линейное время получим суффиксный массив <tex> A_{S_e} </tex> для четных суффиксов, используя уже построенный <tex> A_{S_o} </tex>.
Заметим, что сортировка множества четных суффиксов <tex> \{ S[i..n] | i \mod bmod 2 = 0 \} </tex> аналогична сортировке множества пар <tex> \{ (S[i], S[i+1..n]) | i \mod bmod 2 = 0 \} </tex>. Однако <tex> S[i+1..n] </tex> — нечетный суффикс, и его относительную позицию мы уже узнали на шаге 1.
Таким образом, чтобы отсортировать эти пары за линейное время, сначала сразу выпишем их в порядке возрастания второго элемента пары (то есть в порядке вхождения в массив <tex> A_{S_o} </tex>), а потом отсортируем устойчивой сортировкой подсчетом по первым элементам. После этого легко можно восстановить массив <tex> A_{S_e} </tex>:
=== Шаг 1 ===
На этом шаге строится суффиксный массив <tex> A_{S_{12}} </tex> для множества суффиксов <tex> \{ S[i..n-1] | i \mod bmod 3 \ne 0 \} </tex>.
# Получим строку <tex> S' </tex> аналогично предыдущему алгоритму:
#* Сделаем список, состоящий из троек <tex> S[i..i+2]</tex> , где <tex> i \mod bmod 3 \ne 0 </tex>.
#* Отсортируем его за линейное время цифровой сортировкой и получим новый алфавит <tex> \Sigma' </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 \mod bmod 3 = 1 </tex>, в новом алфавите будет соответствовать строка <tex> S'[\frac{i-1}{3}..\frac{n}{3} - 1] </tex>, а если <tex> i\mod 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 \frac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j = 3(A_{S'}[i] - \frac{n}{3}) + 2 </tex> в строке <tex> S </tex>. Псевдокод получения <tex> A_{S_{12}} </tex>:
=== Шаг 2 ===
Этот шаг также аналогичен первой версии алгоритма. Сортировка множества <tex> \{ S[i..n-1] | i \mod bmod 3 = 0 \} </tex> аналогична сортировке пар <tex> \{ (S[i], S[i+1..n-1]) | i \mod bmod 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> = []
{|
| [[Файл:Kark_sanders_stage1.png|325px|thumb| Фаза 1]]|-| [[Файл:Kark_sanders_stage2.png|325px|thumb| Фаза 2]]|-| [[Файл:Kark_sanders_stage3.png|325px|thumb| Фаза 3]]
|}
