74
правки
Изменения
→Пример
=== Пример ===
Построим суффиксный массив для строки '''<tex>abbacab'''</tex>. После добавления защитного символа и дополнения до кратной трем длины, получим '''<tex>abbacab$$'''</tex>.
* '''Суффиксный массив для позиций не кратных 3'''
# Тройками, соответствующими равными 1 по модулю 3 позициям, будут: '''<tex>bba'''</tex>, '''<tex>cab'''</tex>, '''<tex>\$\$\$'''</tex>, соответствующими равным 2 по модулю 3 — '''<tex>bac'''</tex>, '''<tex>ab\$'''</tex>, '''<tex>\$\$\$'''</tex>. Новый алфавит <tex> \Sigma' </tex> будет содержать элементы '''<tex>bba'''</tex>, '''<tex>cab'''</tex>, '''<tex>\$\$\$'''</tex>, '''<tex>bac'''</tex>, '''<tex>ab\$'''</tex>, которые после сортировки получат номера 3, 4, 0, 2, 1 соотвествтенносоответственно.# Строкой '''<tex>bbacab\$\$\$bacab\$\$\$\$''' </tex> в новом алфавите <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].
* '''Суффиксный массив для позиций кратных 3'''
# Обойдя массив <tex> A_{S_{12}} </tex> и выбрав в нем элементы, равные 1 по модулю 3, получим массив пар <tex>M</tex> = [('''<tex>b'''</tex>, 7), ('''<tex>a'''</tex>, 1), ('''<tex>a'''</tex>, 4)]# После устойчивой сортировки подсчетом по первому элементу, получим <tex> M </tex> = [('''<tex>a'''</tex>, 1), ('''<tex>a'''</tex>, 4), ('''<tex>b'''</tex>, 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]).
# После получения относительного порядка суффиксов, получим тройки ('''<tex>a'''</tex>, '''<tex>b'''</tex>, 1) и ('''<tex>a'''</tex>, '''<tex>b'''</tex>, 3). Первая тройка меньше второй, поэтому добавляем суффикс, соответствующий позиции 5 в массив <tex> A_{S} </tex>.
# В конце итерации получаем <tex> A_{S} </tex> = [8, 7, 5], <tex> i </tex> = 3, <tex> j </tex> = 0.
К концу слияния получим <tex> A_{S} </tex> = [8, 7, 5, 0, 3, 6, 2, 1, 4]. Так как мы добавляли один символ '''<tex>\$''' </tex> в начале алгоритма для дополнения строки до длины, кратной трем, выбросим последний суффикс из <tex> A_{S} </tex>, получим в итоге, что <tex> A_{S} </tex> = [7, 5, 0, 3, 6, 2, 1, 4].
{| style="background-color:#CCC;margin:0.5px"
