74
правки
Изменения
→Суффиксный массив для нечетных суффиксов
=====Суффиксный массив для нечетных суффиксов=====
# Отобразим исходную строку <tex> S ^* </tex> длины <tex> n </tex> в строку <tex> S' </tex> длины <tex> \dfrac{n}{2} </tex> следующим образом:#* Сделаем список, состоящий из пар символов вида <tex> S^*[i..i + 1] </tex>, где <tex> i \bmod 2 = 1 </tex>.
#* Отсортируем его цифровой сортировкой за линейное время и получим новый алфавит <tex> \Sigma' </tex>.
#* Перекодируем строку <tex> S^*[1..n] </tex> в алфавит <tex> \Sigma' </tex>, получив строку <tex> S' </tex> половинной длины.
# Рекурсивно построим суффиксный массив <tex> A_{S'} </tex>.
# Построим суффиксный массив <tex> A_{S_o} </tex>. Очевидно, <tex> A_{S_o}[i] = 2 A_{S'}[i] + 1 </tex>, так отношение упорядоченности любых двух строк в старом алфавите <tex> \Sigma </tex> эквивалентно отношению упорядоченности в новом алфавите <tex> \Sigma' </tex> по его построению.
