Изменения

'''Алгоритм КаркайненаКарккайнена-Сандерса ''' (KarkkainenKärkkäinen, Sanders) — алгоритм построения [[суффиксный массив | суффиксного массива]] за линейное время. __TOC__ == Используемые обозначения ==* В данном конспекте используется 0-индексация.* <tex>S[i..j] </tex> — подстрока строки <tex> S </tex> с <tex>i</tex>-го по <tex>j</tex>-й символы включительно.* Пусть длина строки <tex> S </tex> равна <tex> n </tex>. Обозначим <tex> S^*[i..j] </tex>, где <tex> j \geqslant n </tex> как строку <tex> S[i..n-1] </tex>, дополненную защитными символами <tex> \$ </tex> до длины <tex> n </tex>. == Алгоритм «разделяй и властвуй» ==

== Базовая идея ==Алгоритм базируется на алгоритме Фараха<ref>M. Farach. Optimal suffix tree construction with large alphabets. http://www.cs.rutgers.edu/~farach/pubs/FarFerrMuthu00.pdf </ref> построения суффиксного дерева за линейное время:# Строим суффиксное дерево суффиксный массив для четных нечетных суффиксов , рекурсивно сведя задачу к построению суффиксного дерева массива для строки половинной длины.# Строим суффиксное дерево суффиксный массив для нечетных четных суффиксов за линейное время, используя результат для четных позицийпервого шага.# Сливаем суффиксные деревья массивы за линейное время. Получили асимптотическое уравнение <tex> T(n) = T\left( \dfrac{n}{2}\right) + O(n) </tex>, решением которого является <tex> T(n) = O(n) </tex>. Для упрощения алгоритма вначале дополним нашу строку до четной длины (например, добавлением <tex>\$</tex> в конец). На шаге слияния мы сможем избавиться от него.

Получили асимптотическое уравнение =====База рекурсии=====Если длина текущей строки <tex> T(n) = T(\frac{n}{2}) + O(n) S </tex>равна двум, решением которого является <tex> T(n) = O(n) </tex>надо выполнить обычное сравнение суффиксов.

== Алгоритм == Для упрощения алгоритма вначале дополним нашу строку до четной длины (например, добавлением $ в конец). На шаге сливания мы сможем избавиться от него.=Суффиксный массив для нечетных суффиксов== Шаг 1 ===На первом шаге мы строим суффиксный массив <tex> A_{S_e} </tex> для суффиксов строки <tex> S </tex>, начинающихся в четных позициях.

# Отобразим исходную строку <tex> S ^* </tex> длины <tex> n </tex> в строку <tex> S' </tex> длины <tex> \fracdfrac{n}{2} </tex> следующим образом:#* Сделаем список, состоящий из пар символов вида <tex> S^*[2i]S[2i i..i + 1] </tex>, где <tex> i \in [0; n / bmod 2) = 1 </tex>.

#* Перекодируем строку <tex> S ^*[1..n] </tex> в алфавит <tex> \Sigma' </tex>, получив строку <tex> S' </tex> половинной длины.

# Построим суффиксный массив <tex> A_{S_eS_o} </tex>. Очевидно, <tex> A_{S_eS_o}[i] = 2 A_{S'}[i] + 1 </tex>, так отношение упорядоченности любых двух строк в старом алфавите <tex> \Sigma </tex> эквивалентно отношению упорядоченности в новом алфавите <tex> \Sigma' </tex> по его построению.

=== Шаг 2 ==Суффиксный массив для четных суффиксов=====На этом шаге мы за линейное время получим суффиксный массив <tex> A_{S_oS_e} </tex> для четных суффиксов строки, начинающихся в нечетных позициях, используя уже построенный <tex> A_{S_eS_o} </tex>.

Заметим, что сортировка множества нечетных четных суффиксов <tex> \{ S^*[i..n] | \mid i \mod bmod 2 == 1 0 \} </tex> аналогична сортировке множества пар <tex> \{ (S^*[i], S^*[i+1..n]) | \mid i \mod bmod 2 == 1 0 \} </tex>. Однако <tex> S^*[i+1..n] </tex> — четный нечетный суффикс, и его относительную позицию мы уже узнали на шаге 1, то есть свели задачу к сортировке <tex> \{ (S[i], pos_e[i+1]) | i \mod 2 == 1 \} </tex>, где <tex> pos_e[i] </tex> — позиция суффикса <tex> S[i..n] </tex> в <tex>A_{S_e} </tex>.

Таким образом, чтобы отсортировать эти пары за линейное время, сначала сразу выпишем их в порядке возрастания второго элемента пары (то есть в порядке вхождения в массив <tex> A_{S_eS_o} </tex>), а потом отсортируем устойчивой сортировкой подсчетом по первым элементам. Так была потребована четность длины строки, последним суффиксом будет нечетный, ему будет соответствовать пара После этого легко можно восстановить массив <tex> (S[n-1], n) A_{S_e} </tex>. Псевдокод этого шага:

'''for''' i = 0 '''to''' n / 2 - 1 M.add(Pair(S[n<tex> A_{S_o}</tex>[i] -1], n<tex> A_{S_o}</tex>[i])) quick_stable_sort(M) <tex> A_{S_e} </tex> = [] '''for ''' i = 0..'''to''' n/2 - 1: if <tex> A_{S_e}</tex>.add(M[i] .second - 1) Заметим, что массив <tex> M </tex> перед сортировкой подсчетом не был явно отсортирован по вторым элементам, и хранил не суффиксы, а их позиции в строке <tex> S </tex> , но важно, что он был отсортирован по возрастанию соответствующих этим позициям нечетных суффиксов.  Получили, что весь второй шаг требует <tex> O(n) </tex> времени. =====Слияние суффиксных массивов===== 0Для суффиксного дерева третий шаг алгоритма опирается на специфические особенности суффиксных деревьев, которые не присущи суффиксным массивам<ref>M. Farach. Optimal suffix tree construction with large alphabets. http://www.cs.rutgers.edu/~farach/pubs/FarFerrMuthu00.pdf </ref> . В случае [[Суффиксный массив|суффиксного массива]] слияние становится очень сложным, но все же оно было реализовано в алгоритме Ким-Сим-Парк-Парка<ref> D. K. Kim, J. S. Sim, H. Park, and K. Park. Linear-time construction of suffix arrays. http: //перед первым положительным суффиксом ничего www.springerlink.com/content/568156021q45r320/</ref>. Однако простой модификацией алгоритма можно значительно упростить его. === Пример ===Покажем первые два шага агоритма для строки '''ababbbaa'''. Во-первых, добавив защитный символ '''$''', получив строку '''ababbbaa$''' (для этого алгоритма он не требуется, но может стоятьпонадобиться в применениях суффиксного массива). Во-вторых, поэтому пропускаем егодополним ее до четной длины, получив '''ababbbaa$$'''. continue else:=====Суффиксный массив для нечетных суффиксов=====# В новом алфавите <tex> \Sigma' </tex> будет четыре элемента — '''ba''', '''bb''', '''a$''', '''$$'''. После сортировки они получат номера 2, 3, 1 и 0 соответственно. M# Переводим строку <tex>S^*[1..n]</tex> = '''babbbaa$$$''' в новый алфавит. Сжатой строкой <tex> S' </tex> будет '''23210'''.add(Pair(# После рекурсивного вызова получим, что <tex> A_{S'} </tex> = [4, 3, 2, 0, 1], и <tex> A_{S_eS_o}</tex> = [i9, 7, 5, 1, 3] . =====Суффиксный массив для четных суффиксов=====# Обойдя массив <tex> A_{S_o} </tex>, получим <tex> M </tex> = [(<tex>\$</tex>, 9), (<tex>a</tex>-, 7), (<tex>b</tex>, 5), (<tex>a</tex>, 1), (<tex>a</tex>, 3)].# После сортировки подсчетом по первому элементу, получим <tex> M </tex>= [(<tex>\$</tex>, 9), (<tex>a</tex>, 7), (<tex>a</tex>, 1), (<tex>a</tex>, 3), (<tex>b</tex>, 5)].# Восстановив массив <tex> A_{S_e}</tex>, получаем [i8, 6, 0, 2, 4], что действительно является суффиксным массивом для четных суффиксов. =====Слияние суффиксных массивов=====Если бы мы умели сливать <tex> A_{S_o} </tex> и <tex> A_{S_e} </tex> за линейное время, получили бы: {| style="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| №!style="background-color:#EEE"| Подстрока|-|style="background-color:#FFF;padding:2px 30px"| <tex> 9 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> \$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 8 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> \$\$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 7 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> a\$\$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 6 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> aa\$\$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 0 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> ababbbaa\$\$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 2 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> abbbaa\$\$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 5 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> baa\$\$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 1 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> babbbaa\$\$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 4 </tex>))|style="background-color:#FFF;padding:2px 30px"| <tex> bbaa\$\$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 3 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> bbbaa\$\$ </tex>|}

ЗаметимКак и было сказано вначале, что массив <tex> M </tex> явно не отсортирован по вторым элементамизбавиться от лишних '''$''' легко, так как суффиксы, им соответствующие, но главное — что он отсортирован по возрастанию соответствующих вторым элементам суффиксам. После устойчивой сортировки будут первыми в суффиксном массиве (в данном случае достаточно выбросить "9" из суффиксного массива <tex> M </tex> подсчетом по первому элементу легко восстановить массив <tex> A_{S_o} </tex>: <tex> A_{S_o} </tex> = [] for i = 0..n/2 - 1: <tex> A_{S_o} </tex>.add(M[i]).second - 1)

Получилиасимптотическое уравнение <tex> T(n) = T\left(\dfrac23 n\right) + O(n) </tex>, что весь второй шаг требует решением которого также является <tex> T(n) = O(n) </tex> времени(это видно из того, что сумма геометрической прогрессии с основанием <tex> \dfrac23 </tex> равна <tex> 3 </tex>).

Аналогично первой версии алгоритма, дополним строку <tex> S </tex> до длины, кратной трем, защитными символами <tex> \$ </tex> и получим <tex>S^*</tex>. * '''База рекурсии'''Для этого алгоритма минимальной базой рекурсии будет строка длиной 4, так как она дополняется до длины 6, после чего вновь следует рекурсивный вызов строки длиной 4, и, если бы база была меньше 4, алгоритм вошел бы в бесконечную рекурсию. На этом этапе также можно применить обычную сортировку суффиксов, так как это потребует <tex> O(1) </tex> действий. * '''Суффиксный массив для позиций не кратных 3'''На этом шаге строится суффиксный массив <tex> A_{S_{12}} </tex> для множества суффиксов <tex> \{ S^*[i..n-1] \mid i \bmod 3 \ne 0 \} </tex>.# Получим строку <tex> S' </tex> аналогично предыдущему алгоритму:#* Сделаем список, состоящий из троек <tex> S^*[i..i+2]</tex> , где <tex> i \bmod 3 \ne 0 </tex>.#* Отсортируем его за линейное время цифровой сортировкой и получим новый алфавит <tex> \Sigma' </tex>.#* Перекодируем строку <tex> S^*[1..n]S^*[2..n+1] </tex> в строку <tex> S' </tex> длиной <tex> \dfrac23 n </tex> в алфавите <tex> \Sigma' </tex>. Тогда суффиксу <tex> S^*[i..n-1] </tex> в старом алфавите, где <tex> i \bmod 3 =1 </tex>, в новом алфавите будет соответствовать строка <tex> S'\left[\dfrac{i-1}{3}..\dfrac{n}{3} - 1\right] </tex>, а если <tex> i\bmod 3 =2 </tex>, то строка <tex> S'\left[\dfrac{n}{3} + \dfrac{i-2}{3}..\dfrac{2n}{3} - 1\right] </tex>.# Вызовем алгоритм рекурсивно для строки <tex> S' </tex>, получив суффиксный массив <tex> A_{S'} </tex>.# Пройдем по массиву <tex> A_{S'} </tex>. Если <tex> A_{S'}[i] < \dfrac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j = Шаг 3A_{S'}[i] + 1 </tex> в строке <tex> S </tex>, если же <tex> A_{S'}[i] \geqslant \dfrac{n}{3 } </tex>, то этот суффикс соответствует позиции <tex> j = 3\left(A_{S'}[i] - \dfrac{n}{3}\right) + 2 </tex> в строке <tex> S^* </tex>. Псевдокод получения <tex> A_{S_{12}} </tex>: <tex> A_{S_{12}} </tex> =[] '''for''' i =0 '''to''' <tex>A_{S'}</tex>.length - 1: '''if''' <tex>A_{S'}</tex>[i] < n/3: <tex>A_{S_{12}}</tex>.add(3 * <tex>A_{S'}</tex>[i] + 1) '''else''':Для суффиксного дерева третий <tex>A_{S_{12}}</tex>.add(3 * (<tex>A_{S'}</tex>[i] - n/3) + 2) * '''Суффиксный массив для позиций кратных 3'''Этот шаг также аналогичен первой версии алгоритма опирается на специфические особенности . Сортировка множества <tex> \{ S^*[i..n-1] \mid i \bmod 3 = 0 \} </tex> аналогична сортировке пар <tex> \{ (S^*[i], S^*[i+1..n-1]) \mid i \bmod 3 = 0 \} </tex>, где <tex> S^*[i+1..n-1] </tex> — суффиксы в позициях, равных 1 по модулю 3, относительный порядок которых уже известен. Выпишем эти пары в порядке вхождения их в <tex> A_{S_{12}} </tex> и отсортируем по первому элементу устойчивой сортировкой подсчетом, получив суффиксный массив <tex> A_{S_0} </tex>. Псевдокод этого шага:  <tex>A_{S_0}</tex> = [] M = [] '''for''' i = 0 '''to''' 2n/3 - 1: '''if''' <tex> A_{S_{12}}</tex>[i] % 3 == 1: M.add(Pair(S*[<tex>A_{S_{12}}</tex>[i] - 1], <tex>A_{S_{12}}</tex>[i])) stable_sort(M) '''for''' i = 0 '''to''' n/3 - 1: <tex>A_{S_0}</tex>.add(M[i].second - 1)Аналогично, второй шаг требует <tex> O(n) </tex> времени. * '''Слияние суффиксных деревьевмассивов'''На этом шаге мы должны слить суффиксные массивы <tex> A_{S_0} </tex> и <tex> A_{S_{12}} </tex>, которые чтобы получить суффиксный массив <tex> A_{S} </tex> для всей строки <tex> S </tex>. Применим стандартный алгоритм слияния двух отсортированных массивов. Заметим, что явно массивы не присущи суффиксным массивамотсортированы, но соответствующие элементам массива суффиксы — отсортированы. В случае суффиксного массива слияние становится очень сложным Пусть на какой-то итерации слияния мы сравниваем суффиксы, соответствующие позициям <tex> i </tex>, равной 1 по модулю 3, и <tex> j </tex> (она всегда будет равна 0 по модулю 3). Это аналогично сравнению пар <tex> (S^*[i], S^*[i+1..n-1]) </tex> и <tex> (S^*[j], S^*[j+1..n-1]) <ref/tex> D. KСравнить первые элементы пар мы можем за <tex> O(1) </tex>, а относительный порядок вторых элементов пар нам уже известен, так как они соответствуют позициям, равным 2 и 1 по модулю 3 соответственно. Kim Аналогично, пусть на какой-то итерации слияния мы сравниваем суффиксы, соответствующие позициям <tex> i </tex>, равной 2 по модулю 3, Jи <tex> j </tex> (она всегда будет равна 0 по модулю 3). Тогда это аналогично сравнению троек <tex> (S^*[i], S^*[i+1], S^*[i+2. Sim.n-1]) </tex> и <tex> (S^*[j], S^*[j+1], HS^*[j+2. Park.n-1]) </tex>, and Kчто также можно делать за <tex> O(1) </tex>.  Псевдокод этой фазы:  <tex>A_{S}</tex> = [] <font color=green>// Вначале предподсчитаем за O(n) обратную перестановку для суффиксного массива <tex> A_{S_{12}}</tex>, то есть массив rank такой, что <tex> A_{S_{12}}</tex>[rank[i]] = i. Park // Тогда мы сможем за O(1) сравнивать суффиксы по их позиции. Linear-time construction of suffix arrays</font> rank = inverse(<tex>A_{S_{12}}</tex>) '''while''' i < 2 * n/3 '''and''' j < n/3: pos12 = <tex> A_{S_{12}} </tex>[i] pos0 = <tex> A_{0} </tex>[j] '''if''' pos12 % 3 == 1: ''' if''' Pair(S*[pos12], rank[pos12 + 1]) < Pair(S*[pos0], rank[pos0 + 1]): <tex>A_{S}</tex>. httpadd(pos12) i++ '''else''': <tex>A_{S}</tex>.add(pos0) j++ '''else''': '''if''' Triple(S*[pos12], S*[pos12 + 1], rank[pos12 + 2]) < Triple(S*[pos0], S*[pos0 + 1], rank[pos0 + 2]): <tex>A_{S}</wwwtex>.springerlinkadd(pos12) i++ '''else''': <tex>A_{S}</tex>.comadd(pos0) j++ '''while''' i < 2 * n/content3: <tex>A_{S}</568156021q45r320tex>.add(<tex> A_{S_{12}} </tex>[i]) i++ '''while''' j <n/ref3: <tex>A_{S}</tex>. Однако add(<tex> A_{S_{0}} </tex>[j]) j++ Таким образом, получили простой модификацией алгоритма можно значительно упростить егометод слияния за <tex> O(n) </tex>.

Покажем первые два шага агоритма Построим суффиксный массив для строки '''abaaababbacab'''. После добавления защитного символа и дополнения до кратной трем длины, получим '''abbacab$$'''.* '''Суффиксный массив для позиций не кратных 3'''# Тройками, соответствующими равными 1 по модулю 3 позициям, будут: '''bba''', '''cab''', '''$$$''', соответствующими равным 2 по модулю 3 — '''bac''', '''ab$''', '''$$$'''. Новый алфавит <tex> \Sigma' </tex> будет содержать элементы '''bba''', '''cab''', '''$$$''', '''bac''', '''ab$''', которые после сортировки получат номера 3, 4, 0, 2, 1 соответственно.# Строкой '''bbacab$$$bacab$$$$''' в новом алфавите <tex> \Sigma' </tex> будет <tex> S' </tex> = 340210. # После рекурсивного вызова получим <tex> A_{S'} </tex> = [5, 2, 4, 3, 0, 1]. Пересчитав <tex> A_{S_{12}} </tex>, получим [(5 - 3)*3 + 2, 2 * 3 + 1, (4 - 3) * 3 + 2, (3 - 3) * 3 + 2, 0 * 3 + 1, 1 * 3 + 1] = [8, 7, 5, 2, 1, 4].

Во-первых* '''Суффиксный массив для позиций кратных 3'''# Обойдя массив <tex> A_{S_{12}} </tex> и выбрав в нем элементы, равные 1 по модулю 3, получим массив пар <tex>M</tex> = [(<tex>b</tex>, 7), (<tex>a</tex>, 1), (<tex>a</tex>, 4)]# После устойчивой сортировки подсчетом по первому элементу, получим <tex> M </tex> = [('''a''', 1), добавим защитный символ $('''a''', 4), ('''b''', 7)]# Восстановив <tex> A_{S_0} </tex>, получаем [0, 3, получив строку 6].* '''abaaab$Слияние суффиксных массивов'''Рассмотрим, к примеру, третью итерацию слияния, к этой итерации массив <tex> A_{S} </tex> = [8, 7], <tex> i </tex> = 2, <tex> j </tex> = 0, на ней мы сливаем суффиксы, соответствующие позициям 5 и 0. # Образуем тройки <tex>(S^*[5], S^*[6], S^*[7.. Во-вторых8])</tex> и <tex>(S^*[0], S^*[1], дополним ее до четной длиныS^*[2..8])</tex>.# После получения относительного порядка суффиксов, получим тройки ('''a''', '''b''', 1) и ('''a''', получив '''abaaab$$b''', 3). Первая тройка меньше второй, поэтому добавляем суффикс, соответствующий позиции 5 в массив <tex> A_{S} </tex>.# В конце итерации получаем <tex> A_{S} </tex> = [8, 7, 5], <tex> i </tex> = 3, <tex> j </tex> = 0.К концу слияния получим <tex> A_{S} </tex> = [8, 7, 5, 0, 3, 6, 2, 1, 4]. Так как мы добавляли один символ <tex>\$</tex> в начале алгоритма для дополнения строки до длины, кратной трем, выбросим последний суффикс из <tex> A_{S} </tex>, получим в итоге, что <tex> A_{S} </tex> = [7, 5, 0, 3, 6, 2, 1, 4].

{| style="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| №!style="background-color:#EEE"| Подстрока|-|style="background-color:#FFF;padding:2px 30px"| <tex> 8 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> \$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 7 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> \$\$ </tex>|-|style= Шаг 1 "background-color:#FFF;padding:2px 30px"| <tex> 5 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> ab\$\$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 0 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> abbacab\$\$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 3 </tex>|style="background-color:# В новом алфавите FFF;padding:2px 30px"| <tex> acab\$\Sigma' $ </tex> будет три элемента — '''ab''', '''aa''', '''|-|style="background-color:#FFF;padding:2px 30px"| <tex> 6 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> b\$\$'''. Они получат номера </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 2, </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> bacab\$\$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 1 и 0 соответственно.</tex>|style="background-color:# Сжатой строкой FFF;padding:2px 30px"| <tex> S' bbacab\$\$ </tex> будет '''2120'''.|-|style="background-color:# После рекурсивного вызова получим, что FFF;padding:2px 30px"| <tex> A_{S'} 4 </tex> |style= [3"background-color:#FFF;padding:2px 30px"| <tex> cab\$\$ </tex>|}Заметим, 1, 2, 0]что № 9 будет выброшен, и так как в начале алгоритма был добавлен один <tex> A_{S_e} \$ </tex> = к строке {|| [[Файл:Kark_sanders_stage1.png|325px|thumb| Фаза 1]]| [[6, Файл:Kark_sanders_stage2.png|325px|thumb| Фаза 2, 4, 0]]| [[Файл:Kark_sanders_stage3.png|325px|thumb| Фаза 3]]|}

==== Шаг 2 ==Обобщение алгоритма ==# Обойдя массив <tex> A_{S_e} </tex>, получим M = Массив LCP можно получить за линейное время [[('''b''', 6), ('''b''', 2), ('''a''', 4), ('''$''', 8)]Алгоритм_Касаи_и_др.# После сортировки подсчетом по первому элементу, получим M = [('''$''', 8), ('''a''', 4), ('''b''', 6), ('''b''', 2)| алгоритмом Касаи].# Восстановив массив <tex> A_{S_o} </tex>, получаем [7, 3, 5, 1], что действительно является суффиксным массивом для нечетных суффиксов.

На самом деле, алгоритм можно обобщить<ref name== Алгоритм skew == Изменим изначальный алгоритм следующим образом"generalisation"> Juha Kärkkäinen, Peter Sanders and Stefan Burkhardt. Linear work suffix array construction. http:# Построим суффиксный массив для //www.cs.helsinki.fi/juha.karkkainen/publications/jacm05-revised.pdf </ref>, взяв на первом шаге, к примеру, суффиксы, позиции которых по модулю 7 дают 3, 5 и 6. Для этого потребуются некоторое усложнение алгоритма, например, сортировка оставшихся суффиксовв нескольких группах на шаге 2 и слияние нескольких групп на шаге 3, соответствующих не кратным трем позициямно основная идея алгоритма остается той же. Рекурсивно сведем это к построению суффиксного массива для строки длиной в две трети исходнойМножества, которые можно выбрать, на первом шаге определяются '''разностным покрытием''' (''difference cover'').# Построим суффиксный массив для суффиксов{{Определение|definition='''Разностное покрытие''' (англ. ''difference cover'') <tex> D </tex> по модулю <tex>m </tex> — множество чисел от <tex>0</tex> до <tex>m - 1 </tex> таких, что <tex> \forall i \in [0, соответствующих кратных трем позициямm-1]: \exists j, используя результат первого шага за линейное времяk \in D: i \equiv k - j \pmod m </tex>.# Сливаем эти суффиксные массивы в один за линейное время}} Например, <tex> \{1, 2\} </tex> является разностным покрытием по модулю <tex> 3 </tex>, <tex> \{3, 5, 6\} </tex> является разностным покрытием по модулю <tex> 7 </tex>, а <tex> \{1\} </tex> — не является разностным покрытием по модулю <tex> 2 </tex>, поэтому этот алгоритм не применим к нему. Подробнее узнать, как вычислять разностное покрытие для заданного модуля можно также здесь<ref name="generalisation"/>.

Получили асимптотическое уравнение <tex> T(n) = T(\frac23 n) + O(n) </tex>, решением которого = См. также является <tex> T(n) = O(n) </tex> (это видно из того, что сумма геометрической прогрессии с основанием <tex> \frac23 </tex> равна <tex> 3n </tex>).=* [[Суффиксный массив]]

{{TODO| t = впилить описание сливания }}= Примечания ==<references/>

== Ссылки Источники информации==<references * [[Суффиксный массив]]* [http://www.cs.helsinki.fi/juha.karkkainen/publications/>icalp03.pdf Juha Kärkkäinen and Peter Sanders. Simple linear work suffix array construction]