Изменения

Для упрощения алгоритма вначале дополним нашу строку до четной длины (например, добавлением $ в конец). На шаге слияния мы сможем избавиться от него.

Если длина текущей строки <tex> S </tex> меньше двух, надо выполнить обычное сравнение суффиксов.

На первом шаге мы строим суффиксный массив <tex> A_{S_o} </tex> для нечетных суффиксов строки <tex> 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>.

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

Для суффиксного дерева третий шаг алгоритма опирается на специфические особенности суффиксных деревьев, которые не присущи суффиксным массивам<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>. Однако простой модификацией алгоритма можно значительно упростить его.

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

# В новом алфавите <tex> \Sigma' </tex> будет четыре элемента — '''ba''', '''bb''', '''a$''', '''$$'''. После сортировки они получат номера 2, 3, 1 и 0 соответственно.

# Переводим строку S[1..n] = '''babbbaa$$$''' в новый алфавит. Сжатой строкой <tex> S' </tex> будет '''23210'''.

# После рекурсивного вызова получим, что <tex> A_{S'} </tex> = [4, 3, 2, 0, 1], и <tex> A_{S_o} </tex> = [9, 7, 5, 1, 3].

# Обойдя массив <tex> A_{S_o} </tex>, получим <tex> M </tex> = [('''$''', 9), ('''a''', 7), ('''b''', 5), ('''a''', 1), ('''a''', 3)].

# После сортировки подсчетом по первому элементу, получим <tex> M </tex>= [('''$''', 9), ('''a''', 7), ('''a''', 1), ('''a''', 3), ('''b''', 5)].

# Восстановив массив <tex> A_{S_e} </tex>, получаем [8, 6, 0, 2, 4], что действительно является суффиксным массивом для четных суффиксов.

Если бы мы умели сливать <tex> A_{S_o} </tex> и <tex> A_{S_e} </tex> за линейное время, получили бы:

9 '''$'''