74
правки
Изменения
→Алгоритм Карккайнена-Сандерса
Получили асимптотическое уравнение <tex> T(n) = T\left(\dfrac23 n\right) + O(n) </tex>, решением которого также является <tex> T(n) = O(n) </tex> (это видно из того, что сумма геометрической прогрессии с основанием <tex> \dfrac23 </tex> равна <tex> 3 </tex>).
Аналогично первой версии алгоритма, дополним строку <tex> S </tex> до длины, кратной трем, защитными символами <tex> \$ </tex> и получим <tex>S^*</tex>.
* '''База рекурсии'''
* '''Суффиксный массив для позиций не кратных 3'''
На этом шаге строится суффиксный массив <tex> A_{S_{12}} </tex> для множества суффиксов <tex> \{ S^*[i..n-1] \mid i \bmod 3 \ne 0 \} </tex>.
# Получим строку <tex> S' </tex> аналогично предыдущему алгоритму:
#* Сделаем список, состоящий из троек <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:
* '''Суффиксный массив для позиций кратных 3'''
Этот шаг также аналогичен первой версии алгоритма. Сортировка множества <tex> \{ S^*[i..n-1] \mid i \bmod 3 = 0 \} </tex> аналогична сортировке пар <tex> \{ (S^*[i], S^*[i+1..n-1]) \mid i \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> = []
'''for''' i = 0 '''to''' 2n/3 - 1:
'''if''' <tex> A_{S_{12}}</tex>[i] % 3 == 1:
M.add(Pair(S*[<tex>A_{S_{12}}</tex>[i] - 1], <tex>A_{S_{12}}</tex>[i]))
stable_sort(M)
'''for''' i = 0 '''to''' n/3 - 1:
Применим стандартный алгоритм слияния двух отсортированных массивов. Заметим, что явно массивы не отсортированы, но соответствующие элементам массива суффиксы — отсортированы.
Пусть на какой-то итерации слияния мы сравниваем суффиксы, соответствующие позициям <tex> i </tex>, равной 1 по модулю 3, и <tex> j </tex> (она всегда будет равна 0 по модулю 3). Это аналогично сравнению пар <tex> (S^*[i], S^*[i+1..n-1]) </tex> и <tex> (S^*[j], S^*[j+1..n-1]) </tex>. Сравнить первые элементы пар мы можем за <tex> O(1) </tex>, а относительный порядок вторых элементов пар нам уже известен, так как они соответствуют позициям, равным 2 и 1 по модулю 3 соответственно.
Аналогично, пусть на какой-то итерации слияния мы сравниваем суффиксы, соответствующие позициям <tex> i </tex>, равной 2 по модулю 3, и <tex> j </tex> (она всегда будет равна 0 по модулю 3). Тогда это аналогично сравнению троек <tex> (S^*[i], S^*[i+1], S^*[i+2..n-1]) </tex> и <tex> (S^*[j], S^*[j+1], S^*[j+2..n-1]) </tex>, что также можно делать за <tex> O(1) </tex>.
Псевдокод этой фазы:
pos0 = <tex> A_{0} </tex>[j]
'''if''' pos12 % 3 == 1:
''' if''' Pair(S*[pos12], rank[pos12 + 1]) < Pair(S*[pos0], rank[pos0 + 1]):
<tex>A_{S}</tex>.add(pos12)
i++
j++
'''else''':
'''if''' Triple(S*[pos12], S*[pos12 + 1], rank[pos12 + 2]) < Triple(S*[pos0], S*[pos0 + 1], rank[pos0 + 2]):
<tex>A_{S}</tex>.add(pos12)
i++
* '''Слияние суффиксных массивов'''
Рассмотрим, к примеру, третью итерацию слияния, к этой итерации массив <tex> A_{S} </tex> = [8, 7], <tex> i </tex> = 2, <tex> j </tex> = 0, на ней мы сливаем суффиксы, соответствующие позициям 5 и 0.
# Образуем тройки <tex>(S^*[5], S^*[6], S^*[7..8]) </tex> и <tex>(S^*[0], S^*[1], S^*[2..8])</tex>.
# После получения относительного порядка суффиксов, получим тройки ('''a''', '''b''', 1) и ('''a''', '''b''', 3). Первая тройка меньше второй, поэтому добавляем суффикс, соответствующий позиции 5 в массив <tex> A_{S} </tex>.
# В конце итерации получаем <tex> A_{S} </tex> = [8, 7, 5], <tex> i </tex> = 3, <tex> j </tex> = 0.
