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\'''cab$</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].
