1679
правок
Изменения
→Алгоритм Карккайнена-Сандерса
=== База рекурсии ===
Для этого алгоритма минимальной базой рекурсии будет строка длиной меньшей или равной 4, так как строка длины 4 дополнится она дополняется до строки длины 6, после чего вновь будет следует рекурсивный вызов строки длиной 4, и, если бы база была меньше 4, алгоритм вошел бы в бесконечную рекурсию. На этом этапе также можно применить обычную сортировку суффиксов, так как это потребует <tex> O(1) </tex> действий.
=== Шаг 1 ===
# Пройдем по массиву <tex> A_{S'} </tex>. Если <tex> A_{S'}[i] < \frac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j = 3A_{S'}[i] + 1 </tex> в строке <tex> S </tex>, если же <tex> A_{S'}[i] \ge \frac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j = 3(A_{S'}[i] - \frac{n}{3}) + 2 </tex> в строке <tex> S </tex>. Псевдокод получения <tex> A_{S_{12}} </tex>:
<tex> A_{S_{12}} </tex> = []
'''for ''' i = 0..<tex>A_{S'}</tex>.length - 1: '''if ''' <tex>A_{S'}</tex>[i] < n / 3:
<tex>A_{S_{12}}</tex>.add(3 * <tex>A_{S'}</tex>[i] + 1)
'''else''':
<tex>A_{S_{12}}</tex>.add(3 * (<tex>A_{S'}</tex>[i] - n / 3) + 2)
<tex>A_{S_0}</tex> = []
M = []
'''for ''' i = 0..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..n/3 - 1:
<tex>A_{S_0}</tex>.add(M[i].second - 1)
Аналогично, второй шаг требует <tex> O(n) </tex> времени.
// Тогда мы сможем за O(1) сравнивать суффиксы по их позиции.
rank = inverse(<tex>A_{S_{12}}</tex>)
'''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], rank[pos12 + 1]) < Pair(S[pos0], rank[pos0 + 1]):
<tex>A_{S}</tex>.add(pos12)
i++
'''else''':
<tex>A_{S}</tex>.add(pos0)
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++
'''else''':
<tex>A_{S}</tex>.add(pos0)
j++
'''while ''' i < 2 * n / 3:
<tex>A_{S}</tex>.add(<tex> A_{S_{12}} </tex>[i])
i++
'''while ''' j < n / 3:
<tex>A_{S}</tex>.add(<tex> A_{S_{0}} </tex>[j])
j++
