Изменения

__TOC__

* В данном конспекте используется 0-индексация.

* <tex>S[i..j] </tex> — подстрока строки <tex> S </tex> с <tex>i</tex>-го по <tex>j</tex>-й символы включительно.

== Алгоритм «разделяй и властвуй» ==

# Сливаем суффиксные массивы за линейное время.

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

M = []

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

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

<tex> A_{S_e} </tex>.add(M[i].second - 1)

Получили, что весь второй шаг требует <tex> O(n) </tex> времени.

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

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

Во-первых, добавив защитный символ '''$''', получив строку '''ababbbaa$''' (для этого алгоритма он не требуется, но может понадобиться в применениях суффиксного массива). Во-вторых, дополним ее до четной длины, получив '''ababbbaa$$'''.

# В новом алфавите <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> A_{S_o} </tex> и <tex> A_{S_e} </tex> за линейное время, получили бы:

Как и было сказано вначале, избавиться от лишних '''$''' легко, так как суффиксы, им соответствующие, будут первыми в суффиксном массиве (в данном случае достаточно выбросить "9" из суффиксного массива).

== Алгоритм Карккайнена-Сандерса ==

Изменим изначальный алгоритм следующим образом:

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

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

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

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

<tex>A_{S_{12}}</tex>.add(3 * <tex>A_{S'}</tex>[i] + 1)

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

M = []

stable_sort(M)

<tex>A_{S_0}</tex>.add(M[i].second - 1)

Аналогично, второй шаг требует <tex> O(n) </tex> времени.

На этом шаге мы должны слить суффиксные массивы <tex> A_{S_0} </tex> и <tex> A_{S_{12}} </tex>, чтобы получить суффиксный массив <tex> A_{S} </tex> для всей строки <tex> S </tex>.

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

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

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

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

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

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

i++

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

j++

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

i++

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

j++

<tex>A_{S}</tex>.add(<tex> A_{S_{12}} </tex>[i])

i++

Таким образом, получили простой метод слияния за <tex> O(n) </tex>.

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

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

# После рекурсивного вызова получим <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> M </tex> = [('''a''', 1), ('''a''', 4), ('''b''', 7)]

# Восстановив <tex> A_{S_0} </tex>, получаем [0, 3, 6].

Рассмотрим, к примеру, третью итерацию слияния, к этой итерации массив <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.

Массив 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=

}}

* [[Суффиксный массив]]

* [http://www.cs.helsinki.fi/juha.karkkainen/publications/icalp03.pdf Juha Kärkkäinen and Peter Sanders. Simple linear work suffix array construction]