97
правок
Изменения
м
* [[Суффиксный массив]]* [http://e-maxx.ru/algo/suffix_array e-maxx.ruMAXimal :: algo :: Суффиксный массив]
источники информации, см. также
== Постановка задачи ==
Дана циклическая строка <tex>s[0 .. n - 1]</tex>. Суффиксом циклической строки <tex>s</tex> называется строка <tex>s[i .. n - 1] + s[0 .. i - 1] (, i < n) </tex>. Требуется отсортировать все её суффиксы в порядке лексикографической сортировки.
== Решение ==
Заметим, что циклическая подстрока длины <tex>2^k</tex> состоит из двух подстрок длины <tex>2^{k-1}</tex>, которые мы можем сравнивать между собой за <tex>O(1)</tex>, используя информацию с предыдущей итерации — номера классов эквивалентности <tex>c</tex>. Таким образом, для подстроки длины <tex>2^k</tex>, начинающейся в позиции <tex>i</tex>, вся необходимая информация содержится в паре чисел <tex>(c[i], c[i + 2^{k-1}])</tex>.
Это даёт нам весьма простое решение: отсортировать подстроки длины <tex>2^k</tex> просто по этим парам чисел, это и даст нам требуемый порядок, т.е. массив <tex>p</tex>. Воспользуемся здесь приёмом, на котором основана [[Цифровая сортировка| цифровая сортировка]]: чтобы отсортировать пары, отсортируем их сначала по вторым элементам, а затем — по первым элементам (обязательно устойчивой сортировкой). Однако отдельно вторые элементы уже упорядочены — этот порядок задан в массиве от предыдущей итерации. Тогда, чтобы упорядочить пары по вторым элементам, надо просто от каждого элемента массива <tex>p</tex> отнять <tex>2^{k-1}</tex> — это даст нам порядок сортировки пар по вторым элементам (<tex>p</tex> даёт упорядочение подстрок длины <tex>2^{k-1}</tex>, и при переходе к строке вдвое большей длины эти подстроки становятся их вторыми половинками, поэтому от позиции второй половинки отнимается длина первой половинки).
Таким образом, мы производим сортировку по вторым элементам пар. Теперь надо произвести устойчивую сортировку по первым элементам пар, её уже можно выполнить за <tex>O(n)</tex> с помощью сортировки подсчётом.
cur_len *= 2
'''return''' suffs
== См. также ==
* [[Суффиксный массив]]
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
== Источники ==
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Суффиксный массив]]
