74
правки
Изменения
→База рекурсии
=====База рекурсии=====
Если длина текущей строки <tex> S </tex> меньше двухравна двум, надо выполнить обычное сравнение суффиксов.
=====Суффиксный массив для нечетных суффиксов=====
Таким образом, чтобы отсортировать эти пары за линейное время, сначала сразу выпишем их в порядке возрастания второго элемента пары (то есть в порядке вхождения в массив <tex> A_{S_o} </tex>), а потом отсортируем устойчивой сортировкой подсчетом по первым элементам. После этого легко можно восстановить массив <tex> A_{S_e} </tex>:
M = []
'''for''' i = 0 '''to''' n/2 - 1:
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> .
В случае [[Суффиксный массив|суффиксного массива ]] слияние становится очень сложным, но все же оно было реализовано в алгоритме Ким-Сим-Парк-Парка<ref> D. K. Kim, J. S. Sim, H. Park, and K. Park. Linear-time construction of suffix arrays. http://www.springerlink.com/content/568156021q45r320/</ref>. Однако простой модификацией алгоритма можно значительно упростить его.
=== Пример ===
=====Суффиксный массив для четных суффиксов=====
# Обойдя массив <tex> A_{S_o} </tex>, получим <tex> M </tex> = [('''<tex>\$'''</tex>, 9), ('''<tex>a'''</tex>, 7), ('''<tex>b'''</tex>, 5), ('''<tex>a'''</tex>, 1), ('''<tex>a'''</tex>, 3)].# После сортировки подсчетом по первому элементу, получим <tex> M </tex>= [('''<tex>\$'''</tex>, 9), ('''<tex>a'''</tex>, 7), ('''<tex>a'''</tex>, 1), ('''<tex>a'''</tex>, 3), ('''<tex>b'''</tex>, 5)].
# Восстановив массив <tex> A_{S_e} </tex>, получаем [8, 6, 0, 2, 4], что действительно является суффиксным массивом для четных суффиксов.
<tex>A_{S}</tex> = []
<font color=green>// Вначале предподсчитаем за O(n) обратную перестановку для суффиксного массива <tex> A_{S_{12}}</tex>, то есть массив rank такой, что <tex> A_{S_{12}}</tex>[rank[i]] = i. // Тогда мы сможем за O(1) сравнивать суффиксы по их позиции.</font>
rank = inverse(<tex>A_{S_{12}}</tex>)
'''while''' i < 2 * n/3 '''and''' j < n/3:
|}
== Получение массива LCP Обобщение алгоритма ==
Массив 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=
'''Разностное покрытие''' (англ. ''difference cover'') <tex> D </tex> по модулю <tex>m </tex> — множество чисел от <tex>0</tex> до <tex>m - 1 </tex> таких, что <tex> \forall i \in [0, m-1]: \exists j, k \in D: i \equiv k - j \pmod m </tex>.
}}
Например, <tex> \{1, 2\} </tex> является разностным покрытием по модулю <tex> 3 </tex>, <tex> \{3, 5, 6\} </tex> является разностным покрытием по модулю <tex> 7 </tex>, а <tex> \{1\} </tex> — не является разностным покрытием по модулю <tex> 2 </tex>, поэтому этот алгоритм не применим к нему. Подробнее узнать, как вычислять разностное покрытие для заданного модуля можно также здесь<ref name="generalisation"/>.
