97
правок
Изменения
Нет описания правки
{{Задача
|definition = Дана циклическая строка <tex>s[0 .. n - 1]</tex>. Суффиксом циклической строки <tex>s</tex> называется строка <tex>s[i .. n - 1] + s[0 .. i - 1], i < n </tex> (будем называть такую строкую суффиксом под номером <tex>i</tex>). Требуется отсортировать все её суффиксы в порядке лексикографической сортировки.
Рассматриваемый алгоритм состоит из <tex>\lceil\log n\rceil + 1</tex> итераций. На <tex>k</tex>-той итерации (<tex>k=0..\lceil\log n\rceil </tex>) сортируются циклические подстроки длины <tex>2^k</tex>. На последней, <tex>\lceil\log n\rceil</tex>-ой итерации, будут сортироваться подстроки длины <tex>2^{\lceil\log n\rceil} \geqslant n</tex>, что эквивалентно сортировке циклических сдвигов.
На каждой итерации будем хранить массив перестановки <tex>p[0 .. n - 1]</tex>, где <tex>p[i]</tex> - — номер суффикса, занимающего позицию <tex>i</tex> в текущей перестановке. Также будем хранить массив классов эквивалентности <tex>c[0 .. n - 1]</tex>, где <tex>c[i]</tex> - — класс эквивалентности, которому принадлежит префикс длины <tex>2^k</tex> суффикса под номером <tex>p[i]</tex>. При этом если префикс суффикса под номером <tex>p[i]</tex> лексикографически меньше префикса суффикса под номером <tex>p[j]</tex>, то <tex>c[i] < c[j]</tex>. Если же префиксы равны, то и их классы эквивалентности одинаковы. Так как мы вставили в строку символ <tex>\$</tex>, то к концу алгоритма каждый суффикс будет иметь уникальный класс эквивалентности, значит, мы установим порядок суффиксов.
== Описание алгоритма ==
'''int[]''' calc_positions('''int[]''' count)
count[0] = 0
'''for''' i = 2 .. count.length- 1
count[i] += count[i - 1]
'''return''' count
suffs = '''int'''[str.length]
'''for''' ch '''in''' str
suffs[count[ch]++] = i;
classes = '''int'''[str.length]
classesN = 0
last_char = s[suf[i]]
classesN++
classes[suf] = classesN;
<font color=darkgreen>// нулевая итерация завершена
// сортируем подстроки длиной 2 * cur_len = 2^k</font>
'''while''' cur_len <tex> \leqslant </tex> str.length
<font color=darkgreen>// сортируем по второй половине подстроки</font>
sorted_by2 = '''int'''[str.length]
'''for''' i = 0 .. str.length- 1
sorted_by2[i] = (suffs[i] + str.length - cur_len) '''mod''' str.length
<font color=darkgreen>// сортируем по первой половине
count[classes[by2]]++
count = '''calc_positions'''(count)
'''for''' i = 0 .. str.length- 1
suffs[count[classes[sorted_by2[i]]]++] = sorted_by2[i]
new_classes = '''int'''[str.length]
classesN = 0
'''for''' i = 0 .. str.length- 1
mid1 = (suffs[i] + cur_len) '''mod''' str.length
mid2 = (suffs[i - 1] + cur_len) '''mod''' str.length
'''if''' classes[suffs[i]] <tex> \neq </tex> classes[suffs[i-1]] '''or''' classes[mid1] <tex> \neq </tex> classes[mid2]
classesN++
new_classes[suffs[i]] = classesN
classes = new_classes
