Изменения

Согласно [[Суффиксный массив|определению]] суффиксного массива, для его построения достаточно отсортировать все суффиксы строки. Заменим сортировку суффиксов строки <tex>\alpha</tex> на сортировку циклических сдвигов строки <tex>\alpha\$</tex>, где символ <tex>\$</tex> строго меньше любого символа из <tex>\alpha</tex>. Тогда если в упорядоченных циклических сдвигах отбросить суффикс, начинающийся на <tex>\$</tex>, то получатся упорядоченные суффиксы исходной строки <tex>\alpha</tex>. В дальнейшем положим <tex>|\alpha\$| = n </tex> (заметим, что все циклические сдвиги также имеют длину <tex>Nn</tex>), а также <tex>\alpha\$ = s</tex>.