1679
правок
Изменения
Нет описания правки
Алгоритм КаркайненаКарккайнена-Сандерса (Karkkainen, Sanders) — алгоритм построения [[суффиксный массив | суффиксного массива]] за линейное время.
== Базовая идея ==
# Восстановив массив <tex> A_{S_e} </tex>, получаем [8, 2, 6, 4, 0], что действительно является суффиксным массивом для четных суффиксов.
== Алгоритм КаркайненаКарккайнена-Сандерса ==
Изменим изначальный алгоритм следующим образом:
# Построим суффиксный массив для суффиксов, соответствующих не кратным трем позициям. Рекурсивно сведем это к построению суффиксного массива для строки длиной в две трети исходной.
