1679
правок
Изменения
Нет описания правки
<tex>A_{S}</tex> = []
// Вначале предподсчитаем за O(n) обратные перестановки для суффиксных массивов, то есть массивы order rank такие, что A[orderrank[i]] = i.
// Тогда мы сможем за O(1) сравнивать суффиксы по их позиции.
while i < 2 * n / 3 and j < n / 3:
pos12 = <tex> A_{S_{12}} </tex>[i]
pos0 = <tex> A_{0} </tex>[j]
if pos12 % 3 == 1:
if Pair(S[pos12], order12rank12[pos12 + 1]) < Pair(S[pos0], order0rank0[pos0 + 1]):
<tex>A_{S}</tex>.add(pos12)
i++
j++
else:
if Triple(S[pos12], S[pos12 + 1], order12rank12[pos12 + 2]) < Triple(S[pos0], S[pos0 + 1], order0rank0[pos0 + 2]):
<tex>A_{S}</tex>.add(pos12)
i++
Таким образом, получили простой метод слияния за <tex> O(n) </tex>.
== Получение 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\ ( \mod 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"/>
== Ссылки ==
<references />
== Источники ==
* [[Суффиксный массив]]
* [http://www.cs.helsinki.fi/juha.karkkainen/publications/icalp03.pdf Juha Kärkkäinen and Peter Sanders. Simple linear work suffix array construction]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Суффиксный массив]]
