Изменения

Аналогично первой версии алгоритма, дополним строку <tex> S </tex> до длины, кратной трем, защитными символами <tex> \$ </tex>.

Для этого алгоритма минимальной базой рекурсии будет строка длиной 4, так как она дополняется до длины 6, после чего вновь следует рекурсивный вызов строки длиной 4, и, если бы база была меньше 4, алгоритм вошел бы в бесконечную рекурсию. На этом этапе также можно применить обычную сортировку суффиксов, так как это потребует <tex> O(1) </tex> действий.

На этом шаге строится суффиксный массив <tex> A_{S_{12}} </tex> для множества суффиксов <tex> \{ S[i..n-1] | i \bmod 3 \ne 0 \} </tex>.

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

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

Этот шаг также аналогичен первой версии алгоритма. Сортировка множества <tex> \{ S[i..n-1] | i \bmod 3 = 0 \} </tex> аналогична сортировке пар <tex> \{ (S[i], S[i+1..n-1]) | i \bmod 3 = 0 \} </tex>, где <tex> S[i+1..n-1] </tex> — суффиксы в позициях, равных 1 по модулю 3, относительный порядок которых уже известен. Выпишем эти пары в порядке вхождения их в <tex> A_{S_{12}} </tex> и отсортируем по первому элементу устойчивой сортировкой подсчетом, получив суффиксный массив <tex> A_{S_0} </tex>. Псевдокод этого шага:

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

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

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

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

# Тройками, соответствующими равными 1 по модулю 3 позициям, будут: '''bba''', '''cab''', '''$$$''', соответствующими равным 2 по модулю 3 — '''bac''', '''ab$''', '''$$$'''. Новый алфавит <tex> \Sigma' </tex> будет содержать элементы '''bba''', '''cab''', '''$$$''', '''bac''', '''ab$''', которые после сортировки получат номера 3, 4, 0, 2, 1 соотвествтенно.

# Строкой '''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_{12}} </tex> и выбрав в нем элементы, равные 1 по модулю 3, получим массив пар <tex>M</tex> = [('''b''', 7), ('''a''', 1), ('''a''', 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.

# Образуем тройки (S[5], S[6], S[7..8]) и (S[0], S[1], S[2..8]).