Изменения
Новая страница: «{{В разработке}} Дана строка <tex>s</tex>. Требуется отсортировать все её суффиксы. Поскольку мы …»
{{В разработке}}
Дана строка <tex>s</tex>. Требуется отсортировать все её суффиксы.
Поскольку мы сортируем циклические сдвиги, то и подстроки мы будем рассматривать циклические: под подстрокой <tex>s[i..j]</tex>, когда <tex>i > j</tex>, понимается подстрока <tex>s[i..n-1] + s[0..j]</tex>. Кроме того, предварительно все индексы берутся по модулю длины строки.
Рассматриваемый алгоритм состоит из примерно <tex>\log n</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} \ge n</tex>, что эквивалентно сортировке циклических сдвигов.
На каждой фазе алгоритм помимо перестановки <tex>p[0..n-1]</tex> индексов циклических подстрок будет поддерживать для каждой циклической подстроки, начинающейся в позиции <tex>i</tex> с длиной <tex>2^k</tex>, номер класса эквивалентности <tex>c[i]</tex>, которому эта подстрока принадлежит. В самом деле, среди подстрок могут быть одинаковые, и алгоритму понадобится информация об этом. Кроме того, номера классов эквивалентности <tex>c[i]</tex>, будем давать таким образом, чтобы они сохраняли и информацию о порядке: если один суффикс меньше другого, то и номер класса он должен получить меньший.
Перейдём теперь к более подробному описанию алгоритма
На нулевой фазе мы должны отсортировать циклические подстроки длины <tex>1</tex>, т.е. отдельные символы строки, и разделить их на классы эквивалентности (одинаковые символы должны быть отнесены к одному классу эквивалентности). Это можно сделать сортировкой подсчётом. Для каждого символа посчитаем, сколько раз он встретился. Потом по этой информации восстановим массив <tex>p</tex>. После этого, проходом по массиву <tex>p</tex> и сравнением символов, строится массив <tex>c</tex>.
Далее, пусть мы выполнили <tex>k-1-</tex>ю фазу (т.е. вычислили значения массивов <tex>p</tex> и <tex>c</tex> для неё). Научимся за <tex>O(n)</tex> выполнять следующую, <tex>k-</tex>ю, фазу. Поскольку фаз всего <tex>O(\log n)</tex>, это даст нам требуемый алгоритм с временем <tex>O(n \log 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])</tex>.
Дана строка <tex>s</tex>. Требуется отсортировать все её суффиксы.
Поскольку мы сортируем циклические сдвиги, то и подстроки мы будем рассматривать циклические: под подстрокой <tex>s[i..j]</tex>, когда <tex>i > j</tex>, понимается подстрока <tex>s[i..n-1] + s[0..j]</tex>. Кроме того, предварительно все индексы берутся по модулю длины строки.
Рассматриваемый алгоритм состоит из примерно <tex>\log n</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} \ge n</tex>, что эквивалентно сортировке циклических сдвигов.
На каждой фазе алгоритм помимо перестановки <tex>p[0..n-1]</tex> индексов циклических подстрок будет поддерживать для каждой циклической подстроки, начинающейся в позиции <tex>i</tex> с длиной <tex>2^k</tex>, номер класса эквивалентности <tex>c[i]</tex>, которому эта подстрока принадлежит. В самом деле, среди подстрок могут быть одинаковые, и алгоритму понадобится информация об этом. Кроме того, номера классов эквивалентности <tex>c[i]</tex>, будем давать таким образом, чтобы они сохраняли и информацию о порядке: если один суффикс меньше другого, то и номер класса он должен получить меньший.
Перейдём теперь к более подробному описанию алгоритма
На нулевой фазе мы должны отсортировать циклические подстроки длины <tex>1</tex>, т.е. отдельные символы строки, и разделить их на классы эквивалентности (одинаковые символы должны быть отнесены к одному классу эквивалентности). Это можно сделать сортировкой подсчётом. Для каждого символа посчитаем, сколько раз он встретился. Потом по этой информации восстановим массив <tex>p</tex>. После этого, проходом по массиву <tex>p</tex> и сравнением символов, строится массив <tex>c</tex>.
Далее, пусть мы выполнили <tex>k-1-</tex>ю фазу (т.е. вычислили значения массивов <tex>p</tex> и <tex>c</tex> для неё). Научимся за <tex>O(n)</tex> выполнять следующую, <tex>k-</tex>ю, фазу. Поскольку фаз всего <tex>O(\log n)</tex>, это даст нам требуемый алгоритм с временем <tex>O(n \log 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])</tex>.
