Алгоритм цифровой сортировки суффиксов циклической строки

Постановка задачи

Дана циклическая строка [math]s[0 .. n - 1][/math]. Суффиксом циклической строки [math]s[/math] называется строка [math]s[i .. n - 1] + s[0 .. i - 1], i \lt n [/math]. Требуется отсортировать все её суффиксы в порядке лексикографической сортировки.

Решение

Рассматриваемый алгоритм состоит из [math]\lceil\log n\rceil + 1[/math] итераций. На [math]k[/math]-той итерации ([math]k=0..\lceil\log n\rceil [/math]) сортируются циклические подстроки длины [math]2^k[/math]. На последней, [math]\lceil\log n\rceil[/math]-ой итерации, будут сортироваться подстроки длины [math]2^{\lceil\log n\rceil} \ge n[/math], что эквивалентно сортировке циклических сдвигов.

На каждой итерации алгоритм помимо перестановки [math]p[0..n-1][/math] индексов циклических подстрок будет поддерживать для каждой циклической подстроки длиной [math]2^k[/math], начинающейся в позиции [math]i[/math], номер класса эквивалентности [math]c[i][/math], которому эта подстрока принадлежит. В самом деле, среди подстрок могут быть одинаковые, и алгоритму понадобится информация об этом. Кроме того, номера классов эквивалентности [math]c[i][/math] будем давать таким образом, чтобы они сохраняли и информацию о порядке: если один суффикс меньше другого, то и номер класса он должен получить меньший.

Описание алгоритма

На нулевой итерации мы должны отсортировать циклические подстроки длины [math]1[/math], т.е. первые символы строк, и разделить их на классы эквивалентности (одинаковые символы должны быть отнесены к одному классу эквивалентности). Это можно сделать сортировкой подсчетом. Для каждого символа посчитаем, сколько раз он встретился. Потом по этой информации восстановим массив [math]p[/math]. После этого проходом по массиву [math]p[/math] и сравнением символов строится массив [math]c[/math].

Пусть мы выполнили [math]k-1[/math]-ю итерацию (т.е. вычислили значения массивов [math]p[/math] и [math]c[/math] для неё). Научимся за [math]O(n)[/math] выполнять [math]k[/math]-ю итерацию. Поскольку итераций всего [math]O(\log n)[/math], это даст нам требуемый алгоритм с временем [math]O(n \log n)[/math].

Заметим, что циклическая подстрока длины [math]2^k[/math] состоит из двух подстрок длины [math]2^{k-1}[/math], которые мы можем сравнивать между собой за [math]O(1)[/math], используя информацию с предыдущей итерации — номера классов эквивалентности [math]c[/math]. Таким образом, для подстроки длины [math]2^k[/math], начинающейся в позиции [math]i[/math], вся необходимая информация содержится в паре чисел [math](c[i], c[i + 2^{k-1}])[/math].

Это даёт нам весьма простое решение: отсортировать подстроки длины [math]2^k[/math] просто по этим парам чисел, это и даст нам требуемый порядок, т.е. массив [math]p[/math]. Воспользуемся здесь приёмом, на котором основана цифровая сортировка: чтобы отсортировать пары, отсортируем их сначала по вторым элементам, а затем — по первым элементам (обязательно устойчивой сортировкой). Однако отдельно вторые элементы уже упорядочены — этот порядок задан в массиве от предыдущей итерации. Тогда, чтобы упорядочить пары по вторым элементам, надо просто от каждого элемента массива [math]p[/math] отнять [math]2^{k-1}[/math] — это даст нам порядок сортировки пар по вторым элементам ([math]p[/math] даёт упорядочение подстрок длины [math]2^{k-1}[/math], и при переходе к строке вдвое большей длины эти подстроки становятся их вторыми половинками, поэтому от позиции второй половинки отнимается длина первой половинки).

Таким образом, мы производим сортировку по вторым элементам пар. Теперь надо произвести устойчивую сортировку по первым элементам пар, её уже можно выполнить за [math]O(n)[/math] с помощью сортировки подсчётом.

Осталось только пересчитать номера классов эквивалентности [math]c[/math], просто пройдя по полученной новой перестановке [math]p[/math] и сравнивая соседние элементы (опять же, сравнивая как пары двух чисел).

Пример

s = abacaba$

[math] \begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|} \hline \multicolumn{3}{|l|}{0 iteration} & \multicolumn{4}{l|}{1 iteration} & \multicolumn{4}{l|}{2 iteration} & \multicolumn{4}{l|}{3 iteration} \\ \hline p & & c & p & & & c & p & & & c & p & & & c \\ \hline 7 & \$ & 1 & 7 & \$a & \textless1, 2\textgreater & 1 & 7 & \$aba & \textless1, 5\textgreater & 1 & 7 & \$abacaba & \textless1, 8\textgreater & 1 \\ \hline 0 & a & 2 & 6 & a\$ & \textless2, 1\textgreater & 2 & 6 & a\$ab & \textless2, 3\textgreater & 2 & 6 & a\$abacab & \textless2, 5\textgreater & 2 \\ \hline 2 & a & 2 & 0 & ab & \textless2, 3\textgreater & 3 & 4 & aba\$ & \textless3, 2\textgreater & 3 & 4 & aba\$abac & \textless3, 4\textgreater & 3 \\ \hline 4 & a & 2 & 4 & ab & \textless2, 3\textgreater & 3 & 0 & abac & \textless3, 4\textgreater & 4 & 0 & abacaba\$ & \textless4, 3\textgreater & 4 \\ \hline 6 & a & 2 & 2 & ac & \textless2, 4\textgreater & 4 & 2 & acab & \textless4, 3\textgreater & 5 & 2 & acaba\$ab & \textless5, 2\textgreater & 5 \\ \hline 1 & b & 3 & 1 & ba & \textless3, 1\textgreater & 5 & 5 & ba\$a & \textless5, 1\textgreater & 6 & 5 & ba\$abaca & \textless6, 7\textgreater & 6 \\ \hline 5 & b & 3 & 5 & ba & \textless3, 1\textgreater & 5 & 1 & baca & \textless5, 6\textgreater & 7 & 1 & bacaba\$a & \textless7, 6\textgreater & 7 \\ \hline 3 & c & 4 & 3 & ca & \textless4, 1\textgreater & 6 & 3 & caba & \textless6,5\textgreater & 8 & 3 & caba\$aba & \textless8, 1\textgreater & 8 \\ \hline \end{tabular} [/math]

Псевдокод

   /* преобразует масив count, так что
      теперь он содержит позиции в массиве suffs с которых 
      необходимо вставлять подстроки, начинающиеся с соответствующих символов */
   calc_positions(count)
       count[0] = 0
       for i = 2 .. count.length
           count[i] += count[i - 1]
      
   /* принимает строку, для которой требуется построить суффиксный массив
      возвращает суффиксный массив */
   suff_array(str)
       s += '$'
       ALPHABET = 255
       
       // нулевая итерация
       count = int[max(ALPHABET, str.length)]
       fill(count, 0)
       for ch in str
           count[ch]++
       calc_positions(count)
       // suffs будет хранить индексы начал отсортированных подстрок текущей длины
       suffs = int[str.length]
       for ch in str
           suffs[count[ch]++] = i;
       classes = int[str.length]
       classesN = 0
       last_char = '$'
       for suf in suffs
           if s[suf] != last_char
               last_char = s[suf[i]]
               classesN++
           classes[suf] = classesN;
       
       // нулевая итерация завершена
       // сортируем подстроки длиной 2 * cur_len = 2^k
       curr_len = 1
       while cur_len <= str.length
           // сортируем по второй половине подстроки
           sorted_by2 = int[str.length]
           for i = 0 .. str.length
               if suffs[i] < cur_len
                   sorted_by2[i] = suffs[i] + str.length() - cur_len
               else
                   sorted_by2[i] = suffs[i] - cur_len
           // сортируем по первой половине
           // сортировка устойчивая, значит получим целиком отсортированные подстроки
           fill(count, 0)
           for by2 in sorted_by2
               count[classes[by2]]++
           calc_positions(count)
           for i = 0 .. str.length
               suffs[count[classes[sorted_by2[i]]]++] = sorted_by2[i]
           
           new_classes = int[str.length]
           classesN = 0
           for i = 0 .. str.length
               mid1 = (suffs[i] + cur_len) % str.length
               mid2 = (suffs[i - 1] + cur_len) % str.length
               if classes[suffs[i]] != classes[suffs[i-1]] or classes[mid1] != classes[mid2]
                   classesN
               new_classes[suffs[i]] = classesN
           classes = new_classes
           cur_len *= 2
       return suffs

См. также

• Суффиксный массив
• Построение суффиксного массива с помощью стандартных методов сортировки

Источники

• MAXimal :: algo :: Суффиксный массив