Алгоритм цифровой сортировки суффиксов циклической строки — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(описание алгоритма)
м (rollbackEdits.php mass rollback)
 
(не показано 17 промежуточных версий 6 участников)
Строка 1: Строка 1:
== Постановка задачи ==
+
{{Задача
 
+
|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>s[0 .. n - 1]</tex>. Суффиксом циклической строки <tex>s</tex> называется строка <tex>s[i .. n - 1] + s[0 .. i - 1], i < n </tex> (будем называть такую строкую суффиксом под номером i). Требуется отсортировать все её суффиксы в порядке лексикографической сортировки.
+
}}
  
 
== Решение ==
 
== Решение ==
Рассматриваемый алгоритм состоит из <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} \ge n</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>2^k</tex>, начинающейся в позиции <tex>i</tex>, номер  класса эквивалентности <tex>c[i]</tex>, которому эта подстрока принадлежит. В самом деле, среди подстрок могут быть одинаковые, и алгоритму понадобится информация об этом. Кроме того, номера  классов эквивалентности <tex>c[i]</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>, то к концу алгоритма каждый суффикс будет иметь уникальный класс эквивалентности, значит, мы установим порядок суффиксов.
  
 
== Описание алгоритма ==
 
== Описание алгоритма ==
Строка 12: Строка 12:
 
На нулевой итерации отсортируем циклические подстроки длины <tex>1</tex>, т.е. первые символы строк, и разделим их на классы эквивалентности (одинаковые символы должны быть отнесены к одному классу эквивалентности). При помощи [[Сортировка подсчетом|сортировки подсчетом]] построим массив <tex>p</tex>, содержащий номера суффиксов, отсортированных в лексикографическом порядке. По этому массиву построим массив классов эквивалентности <tex>c</tex>.
 
На нулевой итерации отсортируем циклические подстроки длины <tex>1</tex>, т.е. первые символы строк, и разделим их на классы эквивалентности (одинаковые символы должны быть отнесены к одному классу эквивалентности). При помощи [[Сортировка подсчетом|сортировки подсчетом]] построим массив <tex>p</tex>, содержащий номера суффиксов, отсортированных в лексикографическом порядке. По этому массиву построим массив классов эквивалентности <tex>c</tex>.
  
На <tex>k</tex>-ой итерации имеем массивы <tex>p</tex> и <tex>c</tex>, вычисленные на предыдущей итерации. Приведем алгоритм, выполняющий <tex>k</tex>-ую итерацию за <tex>O(n)</tex>. Поскольку итераций всего <tex>O(\log n)</tex>, такой алгоритм имеет асимптотику <tex>O(n \log n)</tex>.
+
На <tex>k</tex>-ом проходе имеем массивы <tex>p</tex> и <tex>c</tex>, вычисленные на предыдущей итерации. Приведем алгоритм, выполняющий <tex>k</tex>-ый проход за <tex>O(n)</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>\langle c[i], c[i + 2^{k-1}]\rangle </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>\textless c[i], c[i + 2^{k-1}]\textgreater </tex>.
+
[[Файл:Suff_array.png|350px|thumb|right|Циклическая подстрока длины <tex>2^k</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>2^k</tex> по данным парам и запишем порядок в массив <tex>p</tex>. Воспользуемся здесь приёмом, на котором основана [[Цифровая сортировка| цифровая сортировка]]: отсортируем пары сначала по вторым элементам, а затем по первым (устойчивой сортировкой). Однако вторые элементы уже упорядочены — этот порядок задан в массиве  от предыдущей итерации. Тогда, чтобы получить порядок пар по вторым элементам, надо от каждого элемента массива <tex>p</tex> отнять <tex>2^{k-1}</tex> (<tex>p</tex> даёт упорядочение подстрок длины <tex>2^{k-1}</tex>, и при переходе к строке вдвое большей длины эти подстроки становятся их вторыми половинками, поэтому от позиции второй половинки отнимается длина первой половинки).
Строка 23: Строка 25:
  
 
==Пример==
 
==Пример==
s = abacaba$
 
 
 
<tex>
 
<tex>
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|}
+
s = abacaba\$ \\
\hline
+
i' = i + 2^{k-1} \\
\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}
 
 
</tex>
 
</tex>
 +
{| class="wikitable" style="text-align: center;"
 +
! colspan="3" | 0 фаза
 +
! colspan="4" | 1 фаза
 +
! colspan="4" | 2 фаза
 +
! colspan="4" | 3 фаза
 +
|-
 +
| p
 +
| s
 +
| c
 +
| p
 +
|
 +
|
 +
| c
 +
| p
 +
|
 +
|
 +
| c
 +
| p
 +
|
 +
|
 +
| c
 +
|-
 +
| 7
 +
| $
 +
| 1
 +
| 7
 +
| $a
 +
| 1,2
 +
| 1
 +
| 7
 +
| $aba
 +
| 1,5
 +
| 1
 +
| 7
 +
| $abacaba
 +
| 1,8
 +
| 1
 +
|-
 +
| 0
 +
| a
 +
| 2
 +
| 6
 +
| a$
 +
| 2,1
 +
| 2
 +
| 6
 +
| a$ab
 +
| 2,3
 +
| 2
 +
| 6
 +
| a$abacab
 +
| 2,5
 +
| 2
 +
|-
 +
| 2
 +
| a
 +
| 2
 +
| 0
 +
| ab
 +
| 2,3
 +
| 3
 +
| 4
 +
| aba$
 +
| 3,2
 +
| 3
 +
| 4
 +
| aba$abac
 +
| 3,4
 +
| 3
 +
|-
 +
| 4
 +
| a
 +
| 2
 +
| 4
 +
| ab
 +
| 2,3
 +
| 3
 +
| 0
 +
| abac
 +
| 3,4
 +
| 4
 +
| 0
 +
| abacaba$
 +
| 4,3
 +
| 4
 +
|-
 +
| 6
 +
| a
 +
| 2
 +
| 2
 +
| ac
 +
| 2,4
 +
| 4
 +
| 2
 +
| acab
 +
| 4,3
 +
| 5
 +
| 2
 +
| acaba$ab
 +
| 5,2
 +
| 5
 +
|-
 +
| 1
 +
| b
 +
| 3
 +
| 1
 +
| ba
 +
| 3,1
 +
| 5
 +
| 5
 +
| ba$a
 +
| 5,1
 +
| 6
 +
| 5
 +
| ba$abaca
 +
| 6,7
 +
| 6
 +
|-
 +
| 5
 +
| b
 +
| 3
 +
| 5
 +
| ba
 +
| 3,1
 +
| 5
 +
| 1
 +
| baca
 +
| 5,6
 +
| 7
 +
| 1
 +
| bacaba$a
 +
| 7,6
 +
| 7
 +
|-
 +
| 3
 +
| c
 +
| 4
 +
| 3
 +
| ca
 +
| 4,1
 +
| 6
 +
| 3
 +
| caba
 +
| 6,5
 +
| 8
 +
| 3
 +
| caba$aba
 +
| 8,1
 +
| 8
 +
|}
  
 
==Псевдокод==
 
==Псевдокод==
     /* преобразует масив count, так что
+
     <font color=darkgreen>/* преобразует масив count, так что
 
       теперь он содержит позиции в массиве suffs с которых  
 
       теперь он содержит позиции в массиве suffs с которых  
       необходимо вставлять подстроки, начинающиеся с соответствующих символов */
+
       необходимо вставлять подстроки, начинающиеся с соответствующих символов */</font>
     '''calc_positions'''(count)
+
     '''int[]''' calc_positions('''int[]''' count)
 
         count[0] = 0
 
         count[0] = 0
         '''for''' i = 2 .. count.length
+
         '''for''' i = 2 .. count.length - 1
 
             count[i] += count[i - 1]
 
             count[i] += count[i - 1]
 +
        '''return''' count
 
        
 
        
     /* принимает строку, для которой требуется построить суффиксный массив
+
     <font color=darkgreen>/* принимает строку, для которой требуется построить суффиксный массив
       возвращает суффиксный массив */
+
       возвращает суффиксный массив */</font>
     '''suff_array'''(str)
+
     '''int[]''' suff_array('''string''' str)
 
         s += '$'
 
         s += '$'
        ALPHABET = 255
 
 
          
 
          
         // нулевая итерация
+
         <font color=darkgreen>// нулевая итерация</font>
         count = '''int'''[max(ALPHABET, str.length)]
+
         count = '''int'''[max(<tex>|\Sigma|</tex>, str.length)]
 
         '''fill'''(count, 0)
 
         '''fill'''(count, 0)
 
         '''for''' ch '''in''' str
 
         '''for''' ch '''in''' str
 
             count[ch]++
 
             count[ch]++
         '''calc_positions'''(count)
+
         count = '''calc_positions'''(count)
         // suffs будет хранить индексы начал отсортированных подстрок текущей длины
+
         <font color=darkgreen>// suffs будет хранить индексы начал отсортированных подстрок текущей длины</font>
 
         suffs = '''int'''[str.length]
 
         suffs = '''int'''[str.length]
 
         '''for''' ch '''in''' str
 
         '''for''' ch '''in''' str
             suffs[count[ch]++] = i;
+
             suffs[count[ch]++] = i
 
         classes = '''int'''[str.length]
 
         classes = '''int'''[str.length]
 
         classesN = 0
 
         classesN = 0
 
         last_char = '$'
 
         last_char = '$'
 
         '''for''' suf '''in''' suffs
 
         '''for''' suf '''in''' suffs
             '''if''' s[suf] != last_char
+
             '''if''' s[suf] <tex> \neq </tex> last_char
 
                 last_char = s[suf[i]]
 
                 last_char = s[suf[i]]
 
                 classesN++
 
                 classesN++
             classes[suf] = classesN;
+
             classes[suf] = classesN
 
          
 
          
         // нулевая итерация завершена
+
         <font color=darkgreen>// нулевая итерация завершена
         // сортируем подстроки длиной 2 * cur_len = 2^k
+
         // сортируем подстроки длиной 2 * cur_len = 2^k</font>
         curr_len = 1
+
         cur_len = 1
         '''while''' cur_len <= str.length
+
         '''while''' cur_len <tex> \leqslant </tex> str.length
             // сортируем по второй половине подстроки
+
             <font color=darkgreen>// сортируем по второй половине подстроки</font>
 
             sorted_by2 = '''int'''[str.length]
 
             sorted_by2 = '''int'''[str.length]
             '''for''' i = 0 .. str.length
+
             '''for''' i = 0 .. str.length - 1
                 sorted_by2[i] = (suffs[i] + str.length - cur_len) % str.length
+
                 sorted_by2[i] = (suffs[i] + str.length - cur_len) '''mod''' str.length
             // сортируем по первой половине
+
             <font color=darkgreen>// сортируем по первой половине
             // сортировка устойчивая, значит получим целиком отсортированные подстроки
+
             // сортировка устойчивая, значит получим целиком отсортированные подстроки</font>
 
             '''fill'''(count, 0)
 
             '''fill'''(count, 0)
 
             '''for''' by2 '''in''' sorted_by2
 
             '''for''' by2 '''in''' sorted_by2
 
                 count[classes[by2]]++
 
                 count[classes[by2]]++
             '''calc_positions'''(count)
+
             count = '''calc_positions'''(count)
             '''for''' i = 0 .. str.length
+
             '''for''' i = 0 .. str.length - 1
 
                 suffs[count[classes[sorted_by2[i]]]++] = sorted_by2[i]
 
                 suffs[count[classes[sorted_by2[i]]]++] = sorted_by2[i]
 
              
 
              
 
             new_classes = '''int'''[str.length]
 
             new_classes = '''int'''[str.length]
 
             classesN = 0
 
             classesN = 0
             '''for''' i = 0 .. str.length
+
             '''for''' i = 0 .. str.length - 1
                 mid1 = (suffs[i] + cur_len) % str.length
+
                 mid1 = (suffs[i] + cur_len) '''mod''' str.length
                 mid2 = (suffs[i - 1] + cur_len) % str.length
+
                 mid2 = (suffs[i - 1] + cur_len) '''mod''' str.length
                 '''if''' classes[suffs[i]] != classes[suffs[i-1]] '''or''' classes[mid1] != classes[mid2]
+
                 '''if''' classes[suffs[i]] <tex> \neq </tex> classes[suffs[i-1]] '''or''' classes[mid1] <tex> \neq </tex> classes[mid2]
                     classesN
+
                     classesN++
 
                 new_classes[suffs[i]] = classesN
 
                 new_classes[suffs[i]] = classesN
 
             classes = new_classes
 
             classes = new_classes
Строка 108: Строка 247:
 
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
 
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
  
== Источники ==
+
== Источники информации ==
 
* [http://e-maxx.ru/algo/suffix_array MAXimal :: algo :: Суффиксный массив]
 
* [http://e-maxx.ru/algo/suffix_array MAXimal :: algo :: Суффиксный массив]
 
+
* [http://www.geeksforgeeks.org/suffix-array-set-2-a-nlognlogn-algorithm Suffix Array | Set 2 (nLogn Algorithm)]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Суффиксный массив]]
 
[[Категория: Суффиксный массив]]
 +
[[Категория: Структуры данных]]

Текущая версия на 19:30, 4 сентября 2022

Задача:
Дана циклическая строка [math]s[0 .. n - 1][/math]. Суффиксом циклической строки [math]s[/math] называется строка [math]s[i .. n - 1] + s[0 .. i - 1], i \lt n [/math] (будем называть такую строку суффиксом под номером [math]i[/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} \geqslant n[/math], что эквивалентно сортировке циклических сдвигов.

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

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

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

На [math]k[/math]-ом проходе имеем массивы [math]p[/math] и [math]c[/math], вычисленные на предыдущей итерации. Приведем алгоритм, выполняющий [math]k[/math]-ый проход за [math]O(n)[/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]\langle c[i], c[i + 2^{k-1}]\rangle [/math].

Циклическая подстрока длины [math]2^k[/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] и сравнивая соседние элементы (как пары двух чисел).

Пример

[math] s = abacaba\$ \\ i' = i + 2^{k-1} \\ [/math]

0 фаза 1 фаза 2 фаза 3 фаза
p s c p c p c p c
7 $ 1 7 $a 1,2 1 7 $aba 1,5 1 7 $abacaba 1,8 1
0 a 2 6 a$ 2,1 2 6 a$ab 2,3 2 6 a$abacab 2,5 2
2 a 2 0 ab 2,3 3 4 aba$ 3,2 3 4 aba$abac 3,4 3
4 a 2 4 ab 2,3 3 0 abac 3,4 4 0 abacaba$ 4,3 4
6 a 2 2 ac 2,4 4 2 acab 4,3 5 2 acaba$ab 5,2 5
1 b 3 1 ba 3,1 5 5 ba$a 5,1 6 5 ba$abaca 6,7 6
5 b 3 5 ba 3,1 5 1 baca 5,6 7 1 bacaba$a 7,6 7
3 c 4 3 ca 4,1 6 3 caba 6,5 8 3 caba$aba 8,1 8

Псевдокод

   /* преобразует масив count, так что
      теперь он содержит позиции в массиве suffs с которых 
      необходимо вставлять подстроки, начинающиеся с соответствующих символов */
   int[] calc_positions(int[] count)
       count[0] = 0
       for i = 2 .. count.length - 1
           count[i] += count[i - 1]
       return count
      
   /* принимает строку, для которой требуется построить суффиксный массив
      возвращает суффиксный массив */
   int[] suff_array(string str)
       s += '$'
       
       // нулевая итерация
       count = int[max([math]|\Sigma|[/math], str.length)]
       fill(count, 0)
       for ch in str
           count[ch]++
       count = 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] [math] \neq [/math] last_char
               last_char = s[suf[i]]
               classesN++
           classes[suf] = classesN
       
       // нулевая итерация завершена
       // сортируем подстроки длиной 2 * cur_len = 2^k
       cur_len = 1
       while cur_len [math] \leqslant [/math] str.length
           // сортируем по второй половине подстроки
           sorted_by2 = int[str.length]
           for i = 0 .. str.length - 1
               sorted_by2[i] = (suffs[i] + str.length - cur_len) mod str.length
           // сортируем по первой половине
           // сортировка устойчивая, значит получим целиком отсортированные подстроки
           fill(count, 0)
           for by2 in sorted_by2
               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]] [math] \neq [/math] classes[suffs[i-1]] or classes[mid1] [math] \neq [/math] classes[mid2]
                   classesN++
               new_classes[suffs[i]] = classesN
           classes = new_classes
           cur_len *= 2
       return suffs

См. также

Источники информации