Изменения

=====База рекурсии=====

=====Суффиксный массив для нечетных суффиксов=====

#* Отсортируем его цифровой сортировкой за линейное время и получим новый алфавит <tex> \Sigma' </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> по его построению.

На этом шаге мы за линейное время получим суффиксный массив <tex> A_{S_e} </tex> для четных суффиксов, используя уже построенный <tex> A_{S_o} </tex>.

Таким образом, чтобы отсортировать эти пары за линейное время, сначала сразу выпишем их в порядке возрастания второго элемента пары (то есть в порядке вхождения в массив <tex> A_{S_o} </tex>), а потом отсортируем устойчивой сортировкой подсчетом по первым элементам. После этого легко можно восстановить массив <tex> A_{S_e} </tex>:

M = []

M.add(Pair(S[<tex> A_{S_o}</tex>[i] - 1], <tex> A_{S_o}</tex>[i]))

<tex> A_{S_e} </tex> = []

'''for''' i = 0 '''to''' n/2 - 1:

=====Слияние суффиксных массивов=====

Для суффиксного дерева третий шаг алгоритма опирается на специфические особенности суффиксных деревьев, которые не присущи суффиксным массивам<ref>M. Farach. Optimal suffix tree construction with large alphabets. http://www.cs.rutgers.edu/~farach/pubs/FarFerrMuthu00.pdf </ref> .

=== Пример ===

=====Суффиксный массив для нечетных суффиксов=====

# В новом алфавите <tex> \Sigma' </tex> будет четыре элемента — '''ba''', '''bb''', '''a$''', '''$$'''. После сортировки они получат номера 2, 3, 1 и 0 соответственно.

# После рекурсивного вызова получим, что <tex> A_{S'} </tex> = [4, 3, 2, 0, 1], и <tex> A_{S_o} </tex> = [9, 7, 5, 1, 3].

=====Суффиксный массив для четных суффиксов=====

# Восстановив массив <tex> A_{S_e} </tex>, получаем [8, 6, 0, 2, 4], что действительно является суффиксным массивом для четных суффиксов.

Получили асимптотическое уравнение <tex> T(n) = T\left(\dfrac23 n\right) + O(n) </tex>, решением которого также является <tex> T(n) = O(n) </tex> (это видно из того, что сумма геометрической прогрессии с основанием <tex> \dfrac23 </tex> равна <tex> 3 </tex>).

* '''База рекурсии'''

* '''Суффиксный массив для позиций не кратных 3'''

# Получим строку <tex> S' </tex> аналогично предыдущему алгоритму:

#* Отсортируем его за линейное время цифровой сортировкой и получим новый алфавит <tex> \Sigma' </tex>.

# Вызовем алгоритм рекурсивно для строки <tex> S' </tex>, получив суффиксный массив <tex> A_{S'} </tex>.

<tex> A_{S_{12}} </tex> = []

'''for''' i = 0 '''to''' <tex>A_{S'}</tex>.length - 1:

* '''Суффиксный массив для позиций кратных 3'''

<tex>A_{S_0}</tex> = []

'''for''' i = 0 '''to''' 2n/3 - 1:

'''if''' <tex> A_{S_{12}}</tex>[i] % 3 == 1:

stable_sort(M)

'''for''' i = 0 '''to''' n/3 - 1:

Применим стандартный алгоритм слияния двух отсортированных массивов. Заметим, что явно массивы не отсортированы, но соответствующие элементам массива суффиксы — отсортированы.

Псевдокод этой фазы:

<tex>A_{S}</tex> = []

rank = inverse(<tex>A_{S_{12}}</tex>)

'''while''' i < 2 * n/3 '''and''' j < n/3:

pos0 = <tex> A_{0} </tex>[j]

'''if''' pos12 % 3 == 1:

<tex>A_{S}</tex>.add(pos12)

i++

j++

'''else''':

<tex>A_{S}</tex>.add(pos12)

i++

Построим суффиксный массив для строки '''abbacab'''. После добавления защитного символа и дополнения до кратной трем длины, получим '''abbacab$$'''.

* '''Суффиксный массив для позиций не кратных 3'''

# Строкой '''bbacab$$$bacab$$$$''' в новом алфавите <tex> \Sigma' </tex> будет <tex> S' </tex> = 340210.

# После рекурсивного вызова получим <tex> A_{S'} </tex> = [5, 2, 4, 3, 0, 1]. Пересчитав <tex> A_{S_{12}} </tex>, получим [(5 - 3)*3 + 2, 2 * 3 + 1, (4 - 3) * 3 + 2, (3 - 3) * 3 + 2, 0 * 3 + 1, 1 * 3 + 1] = [8, 7, 5, 2, 1, 4].

* '''Слияние суффиксных массивов'''

Рассмотрим, к примеру, третью итерацию слияния, к этой итерации массив <tex> A_{S} </tex> = [8, 7], <tex> i </tex> = 2, <tex> j </tex> = 0, на ней мы сливаем суффиксы, соответствующие позициям 5 и 0.

# После получения относительного порядка суффиксов, получим тройки ('''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.

|style="background-color:#FFF;padding:2px 30px"| <tex> cab\$\$ </tex>

|}

{|

|}

Массив LCP можно получить за линейное время [[Алгоритм_Касаи_и_др. | алгоритмом Касаи]].

На самом деле, алгоритм можно обобщить<ref name="generalisation"> Juha Kärkkäinen, Peter Sanders and Stefan Burkhardt. Linear work suffix array construction. http://www.cs.helsinki.fi/juha.karkkainen/publications/jacm05-revised.pdf </ref>, взяв на первом шаге, к примеру, суффиксы, позиции которых по модулю 7 дают 3, 5 и 6. Для этого потребуются некоторое усложнение алгоритма, например, сортировка оставшихся суффиксов в нескольких группах на шаге 2 и слияние нескольких групп на шаге 3, но основная идея алгоритма остается той же. Множества, которые можно выбрать, на первом шаге определяются '''разностным покрытием''' (''difference cover'').

{{Определение

|definition=

}}

Например, <tex> \{1, 2\} </tex> является разностным покрытием по модулю <tex> 3 </tex>, <tex> \{3, 5, 6\} </tex> является разностным покрытием по модулю <tex> 7 </tex>, а <tex> \{1\} </tex> — не является разностным покрытием по модулю <tex> 2 </tex>, поэтому этот алгоритм не применим к нему. Подробнее узнать, как вычислять разностное покрытие для заданного модуля можно также здесь<ref name="generalisation"/>.