Изменения

|definition='''Простая строка''' {{---}} строка, которая лексикографически меньше любого своего собственного суффикса.

|definition='''Декомпозиция Линдона''' (англ. ''Lyndon decomposition'') строки <tex>s</tex> {{---}} её разложение <tex>s = s_1s_2...\ldots s_k</tex>, где строки <tex>s_i</tex> просты, и при этом <tex>s_1 \geqslant s_2 \geqslant ... \ldots\geqslant s_k</tex>.

1. Так как <tex>s < t</tex>, то либо <tex>s</tex> является префиксом <tex>t</tex>, тогда: <tex>s + t = s + s + x</tex> <tex>s + s + x < s + x</tex> <tex>s + x < x</tex> Следовательно <tex>t <</tex> любого суффикса <tex>t</tex> (так как по условию <tex>t</tex> явлеяется простой строкой), либо <tex>\exists i : s[i] < t[i]</tex> и <tex>s[j] = t[j]</tex>, <tex>j < i \Rightarrow </tex>. Из обоих ситуаций следует, что <tex> s + t < t</tex>

* <tex>|u| > |t| \Rightarrow s = s' + s''</tex>, <tex>u = s'' + t</tex>. Так как <tex>s</tex> {{---}} простая, то её суффикс <tex> s'' </tex> меньше больше самой строки <tex> s </tex> в каком-то символе, значит, <tex> s + t < s'' + t</tex>

Таким образом доказали даже более сильное утверждение: <tex>s = s_1 s_2 ... \ldots s_k</tex>, <tex> k </tex> {{---}} минимально <tex>\Leftrightarrow</tex> нет <tex>s_i < s_{i+1}</tex>

Пусть существует несколько разбиений <tex>s = s_1s_2...\ldots s_k = s_1's_2'...\ldots s_k'</tex>,

1) Пусть <tex>|s_i| > |s_i'|</tex>, тогда <tex>s_i = s_i's_{i+1}'...\ldots t</tex>, где <tex>t</tex> {{---}} префикс <tex>s_{j+1}'</tex>, <tex>i < j</tex>. Тогда получаем:

n <tex>\leftarrow</tex> |s|.length

Покажем, что алгоритм получает нужное разложение. То есть все <tex>s_i</tex> {{---}} простые, и <tex>s_1 \geqslant s_2 \geqslant ... \ldots \geqslant s_k</tex> лексикографически.

Поиск лексикографически минимального и максимального суффиксов строки {{- --}} вопрос, который часто поднимается при решении различных теоретических задач. С помощью классического алгоритма Дюваля эта задача решается за линейное время и константный размер дополнительной памяти.

Покажем, что <tex>\forall\tau: 1\leleqslant\tau\le\log{n}</tex> существует структура данных, размер которой линейно зависит от длины данного текста, со временем запроса <tex>O(\tau)</tex> и временем препроцессинга <tex>O(n\log{n/\tau})</tex> для запросов на нахождение минимального суффикса.

Будем обозначать <tex>SA(T)</tex> и <tex>ISA(T)</tex> суффиксный массив и инвертированный суффиксный массив строки <tex>T</tex> соответственно. Для данных индексов <tex>i<j</tex> будем обозначать как <tex>Suf[i,j]</tex> массив <tex>\{T[i,i+1, \ldots ,|T|-1], \ldots , T[j,\ldots]\}</tex> - подмассив с индекса <tex>i</tex> по <tex>j+</tex> массива всех суффиксов строки. Множество всех непустых суффиксов строки <tex>Suf[1, \ldots ,|T|-1]\}</tex>будем обозначать для краткости как <tex>Suf</tex>. Также, будем обозначать <tex>SA(T)</tex> и <tex>ISA(T)</tex> [[суффиксный массив]] и инвертированный суффиксный массив строки <tex>T</tex> соответственно. <tex>SA </tex> и <tex>ISA </tex> могут быть улучшены за <tex>O(n)</tex>, чтобы отвечать на запросы вида * по данным подстрокам <tex>x</tex> и <tex>y</tex> строки <tex>T</tex> найти [[Алгоритм Касаи и др.| наибольший общий префикс]] <tex>lcp(x,y)</tex> и определить, какая из подстрок лексикографически меньше

Более того, такой <b>улучшенный суффиксный массив</b> может отвечать на запрос "по данным <tex>x,y</tex> {{---}} подстрокам <tex>T</tex> вычислить максимальное чило <tex>\alpha</tex>, такое, что <tex>x^{\alpha}</tex> является префиксом <tex>y</tex>" за константное время. Действительно, стоит заметить, что если <tex>x</tex> {{---}} префикс <tex>y = T[i \ldots j]</tex>, то <tex>\alpha |x| \leqslant lcp(T[i \ldots j],T[i+|x| \ldots j] < (\alpha+1)|x|)</tex> Запросы к перевёрнутому улучшенному суфмассиву <tex>T^{R}</tex>также имеют смысл. С его помощью мы можем для пары <tex>x,y</tex> подстрок <tex>T</tex> найти их наибольший общий суффикс <tex>lcs(x,y)</tex> и наибольшее число <tex>\alpha</tex>, такое, что <tex>x^{\alpha}</tex> является суффиксом <tex>y</tex>.  Возьмём строку <tex>T</tex> длины <tex>n</tex>. Для каждой позиции <tex>j</tex> мы выберем <tex>O(logN\log{N}) </tex> подстрок <tex>T[k\ldots j]</tex>, которые мы назовём каноническими. Определим как <tex>S^{l}_{j}</tex> <tex>l</tex>-ю кратчайшую каноническую подстроку, заканчивающуюся в позиции <tex>j</tex>. Для пары целых чисел <tex>1\le leqslant i<j\le leqslant n</tex> мы определим как <tex>\alpha(i,j)</tex> наибольшее <tex>l</tex>, такое, что <tex>S^{l}_{j}</tex> {{--- }} суффикс <tex>T[i \ldots j]</tex>.

*<tex>S^{1}_{j} = T[j \ldots j]</tex> и для некоторого <tex>l=O(logN\log{N})</tex> выполняется <tex>S^{l}_{j} = T[1 \ldots j]</tex>*<tex>\forall l:|S^{l+1}_{j}|\le leqslant 2|S^{l}_{j}|</tex>

|statement= Минимальный суффикс Рассмотрим подстроку <tex>T[i\ldots j]</tex> равен либо . Используя улучшенный суффиксный массив строки <tex>T</tex>, за <tex>\mathcal{O}(1)</tex> времени можно найти такой индекс <tex>p\ (i\leqslant p\leqslant j)</tex>, что максимальный суффикс <tex>T[p\mu \ldots j]</tex>, где строки <tex>pT[i \ldots j]</tex>-начальная позиция минимального суффикса в равен либо <tex>Suf(a) T[i,p \ldots j]</tex>, либо минимальному <tex>(b)</tex> максимальному суффиксу строки <tex>|SS_{j}^{\alpha(i,j)}_{j}|</tex>

==Ссылки=Доказательство основной леммы===Ниже мы описываем алгоритм, работающий за константное время, который возвращает позицию <tex>p\in[i,\ j]</tex>. Заметим, что если максимальный суффикс <tex>T[\mu \ldots j]</tex> of <tex>T[i \ldots j]</tex> короче, чем <tex>S_{j}^{\alpha(i,j)}</tex> (случай (b) леммы 7), алгоритм может вернуть любое <tex>p\in[i,\ j]</tex>. Далее мы предполагаем, что <tex>T[\mu \ldots j]</tex> длиннее, чем <tex>S_{j}^{\alpha(i,\ j)}</tex> и показываем, что при этом предположении алгоритм вернёт <tex> p=\mu</tex>. Из нашего предположения свойств канонических подстрок следует, что <tex>\mu\in[i,\ r]</tex>, where <tex>r=j-|S_{j}^{\alpha(i,\ j)}|</tex>, и что длины суффиксов подстроки <tex>T[i \ldots j]</tex>, начинающихся с позиций в промежутке <tex>[i,\ r]</tex>, отличаются не более чем в два раза. Мы начнем со вспомогательной леммы, которая обозначалась как лемма 2 в <ref name="ref1"/> {{Лемма|id=lemma|author=9|statement= Пусть <tex>P_{1}=T[p_{1} \ldots j]</tex> {{---}} префикс строки <tex>T[\mu \ldots j]</tex> и пусть <tex>P_{2}=T[p_{2} \ldots j]</tex>, где <tex>T[p_{2} \ldots j]</tex> {{---}} максимальный суффикс в <tex>Suf [i,\ p_{1}-1]</tex>. Если <tex>P_{1}</tex> не является префиксом <tex>P_{2}</tex>, тогда <tex>\mu=p_{1}</tex>. Иначе, <tex>P_{2}</tex> также является префиксом строки <tex>T[\mu \ldots j]</tex>. |proof= Пусть <tex>T[p_{1} \ldots ]</tex> {{---}} максимальный суффикс в <tex>Suf [i,\ r]</tex> и <tex>T[p_{2} \ldots ]</tex> {{---}} максимальный суффикс в <tex>Suf [i,\ p_{1}-1]</tex>. Очевидно, <tex>P_{1}=T[p_{1} \ldots j]</tex> является префиксом строки <tex>T[\mu \ldots j]</tex>. Предположим, что <tex>P_{1}</tex> {{---}} префикс <tex>P_{2}</tex> (иначе <tex>p_{1}=\mu\</tex> по лемме 9). Длины <tex>P_{1}</tex> и <tex>P_{2}</tex> различаются не более чем в два раза, поэтому <tex>2|P_{1}|\geqslant|P_{2}|</tex>. Благодаря этому, <tex>P_{1}</tex> и <tex>P_{2}</tex> имеют некоторые интересные свойства, описанные в последующих леммах. Эти леммы по существу повторяют леммы 4 и 5 из <ref name="ref1" />, но здесь мы приводим доказательства вследствие другого обозначения.}} {{Лемма|id=lemma|author=10|statement= Подстрока <tex>\rho=T[p_{2} \ldots p_{1}-1]</tex> {{---}} минимальный период строки <tex>P_{2}</tex>, т.е. <tex>\rho</tex> {{---}} кратчайшая строка, такая, что для какого-то <tex>s\geqslant 1</tex> выполняется <tex>P_{2}=\rho^{s}\rho'</tex>.|proof= Поскольку <tex>P_{1}</tex> {{---}} бордер <tex>P_{2},\ \rho=T[p_{2} \ldots p_{1}-1]</tex> {{---}} период <tex>P_{2}</tex>. Остается лишь доказать, что невозможно найти более короткий период. Таким образом, рассмотрим(consider) кратчайший период <tex>\gamma</tex>, и предположим, что <tex>|\gamma|<|\rho|</tex>. Тогда <tex>|\gamma|+|\rho|\leqslant 2|\rho|\leqslant|T[p_{2} \ldots j]|</tex>, и по лемме о периодичности подстрока <tex>P_{2}</tex> имеет другой период <tex>\mathrm{g}\mathrm{c}\mathrm{d}(|\gamma|,\ |\rho|)</tex> . Так как <tex>\gamma</tex> {{---}} кратчайший период, то <tex>|\rho|</tex> должно быть степенью <tex>|\gamma|</tex>, т.е. <tex>\rho=\gamma^{k}</tex> для какого-то <tex>k\geqslant 2</tex>. Предположим, что <tex>T[p_{1} \ldots ]\prec\gamma T[p_{1} \ldots ]</tex> '''(лексикографически меньше)'''. Тогда приписывание к обеим частям последнего неравенства степеней <tex>\gamma</tex> даёт <tex>\gamma^{\ell-1}T[p_{1} \ldots ]\prec\gamma^{\ell}T[p_{1} \ldots ]</tex> для любого <tex>1\leqslant\ell\leqslant k</tex>, таким образом из транзитивности <tex>\prec</tex> получаем <tex>T[p_{1} \ldots ]\prec\gamma^{k}T[p_{1} \ldots ]=T[p_{2} \ldots ]</tex>, что противоречит максимальности <tex>T[p_{1} \ldots ]</tex> in <tex>Suf[i,\ r]</tex>. Таким образом, <tex>T[p_{1} \ldots ]\succ\gamma T[p_{1} \ldots ]</tex>, и следовательно <tex>\gamma^{k-1}T[p_{1} \ldots ]\succ\gamma^{k}T[p_{1} \ldots ]</tex>. Но <tex>\gamma^{k-1}T[p_{1} \ldots ]=T[p_{2}+|\gamma| \ldots ]</tex> и <tex>\gamma^{k}T[p_{1} \ldots ]=T[p_{2} \ldots ]</tex>, поэтому <tex>T[p_{2}+|\gamma| \ldots ]</tex> больше, чем <tex>T[p_{2} \ldots ]</tex> и принадлежит <tex>Suf [i,\ p_{1}-1]</tex>, противоречие. Заметим, что на самом деле <tex>s\geqslant 2</tex>, потому что <tex>2|P_{1}|\geqslant|P_{2}|=|P_{1}|+|\rho|</tex>, поэтому <tex>|P_{1}|\geqslant|\rho|.\ </tex>}} {{Лемма|id=lemma|author=11|statement= Положим, <tex>P_{2}=\rho P_{1}=\rho^{s}\rho'</tex>. Тогда максимальный суффикс <tex>T[\mu \ldots j]</tex> {{---}} длиннейший суффикс строки <tex>T[i \ldots j]</tex> равен <tex>\rho^{t}\rho'</tex> для некоторого <tex>t</tex>. (См. рисунок 1)|proof= Очевидно, что <tex>P_{2}</tex> является бордером <tex>T[\mu \ldots j]</tex>. Из <tex>P_{2}=\rho P_{1}</tex> и <tex>|T[\mu \ldots j]|\leqslant 2|P_{1}|</tex> имеем <tex>|T[\mu \ldots j]|+|\rho|\leqslant 2|P_{1}|+\rho\leqslant 2|P_{2}|</tex>. Следовательно вхождения <tex>P_{2}</tex> в качестве префикса и в качестве суффикса строки <tex>T[\mu \ldots j]</tex> перекрывают друг друга как минимум в <tex>|\rho|</tex> позициях. Т.к. <tex>|\rho|</tex> {{---}} период <tex>P_{2}</tex>, отсюда следует, что <tex>|\rho|</tex> также является периодом <tex>T[\mu \ldots j]</tex>. Таким образом, <tex>T[\mu \ldots j]=\rho''\rho^{r}\rho'</tex>, где <tex>r</tex> {{---}} целое число и <tex>\rho''</tex> {{---}} суффикс <tex>\rho</tex>. Более того, <tex>\rho^{2}</tex> {{---}} это префикс <tex>T[\mu \ldots j]</tex>, поскольку является префиксом <tex>P_{2}</tex>, который в свою очередь является префиксом <tex>T[\mu \ldots j]</tex>. Теперь <tex>\rho''\neq\xi j</tex> будет означать нетривиальное вхождение <tex>\rho</tex> в <tex>\rho^{2}</tex>, которое противоречит примитивности <tex>\rho</tex>, смотри <ref name="ref4">[http://www.google.ru/books?hl=en&lr=&id=PuOOY_DR55UC&oi=fnd&pg=PR7&dq=M.+Crochemore,+C.+Hancart,+and+T.+Lecroq.+Algorithms+on+Strings.+Cambridge+University+Press,+2007&ots=oe_VacDwgA&sig=PKoDRn6K6nZsWfajL0-0jkSlAf8&redir_esc=y#v=onepage&q&f=false M. Crochemore, C. Hancart, and T. Lecroq. Algorithms on Strings. Cambridge University Press, 2007]</ref>. [[Файл:image001.png|Рис. 1. Схематичная иллюстрация к лемме 11.|800px]] '''Рис. 1:''' Схематичная иллюстрация к лемме 11.  Таким образом, <tex>T[\mu \ldots j]=\rho^{r}\rho'</tex>. Если <tex>t>r</tex>, тогда <tex>\rho^{t}\rho'\succ\rho^{r}\rho'</tex>, поэтому <tex>T[\mu \ldots j]</tex> {{---}} длиннейший суффикс строки <tex>T[i \ldots j]</tex>, равный <tex>\rho^{t}\rho'</tex> для некоторого <tex>t</tex>.}}'''Доказательство леммы 7''' <tex>\triangleright</tex> Пусть <tex>T[p_{1} \ldots ]</tex> {{---}} максимальный суффикс в <tex>Suf [i,\ r]</tex> и <tex>T[p_{2} \ldots ]</tex> {{---}} максимальный суффикс в <tex>Suf [i,\ p_{1}-1]</tex>. Сначала вычислим <tex>p_{1}</tex> и <tex>p_{2}</tex> за <tex>\mathcal{O}(1)</tex>, используя улучшенный суффиксный массив. Затем проверим, что <tex>T[p_{1} \ldots j]</tex> является префиксом <tex>T[p_{2} \ldots j]</tex>. Если это неверно, то мы возвращаем <tex>p=p_{1}</tex>. Иначе, мы вычисляем максимальное целое число <tex>r</tex>, такое, что <tex>\rho^{r}</tex> (для <tex>\rho=T[p_{2} \ldots p_{1}-1])</tex>) {{---}} суффикс <tex>T[i \ldots p_{1}-1]</tex>, используя метод из алгоритма поиска минимального суффикса, и возвращаем <tex>p=p_{1}-r|\rho|</tex>. Из вышеописанных лемм следует, что если <tex>T[\mu \ldots j]</tex> длиннее <tex>S_{j}^{\alpha(i,\ j)}</tex>, тогда <tex> p=\mu</tex>. <tex>\triangleleft</tex> ===Построение структуры данных=== Наш алгоритм основывается на следующем понятии. Для <tex>1\leqslant p\leqslant j\leqslant n</tex> мы говорим, что позиция <tex>p</tex> <tex>j</tex>-активна, если не существует такой позиции <tex>p'\in\{p+1,\ \ldots,\ j\}</tex>, что <tex>T[p' \ldots j]\succ T[p \ldots j]</tex>. Другими словами, <tex>p</tex> {{---}} <tex>j</tex>-активна тогда и только тогда, когда <tex>T[p \ldots j]</tex> {{---}} максимальный суффикс самого себя. Максимальный суффикс любой строки является своим собственным максимальным суффиксом, поэтому из определения следует, что стартовая позиция максимального суффикса строки <tex>T[i \ldots j]</tex> {{---}} это минимальная <tex>j</tex>-активная позиция в промежутке <tex>[i,\ j]</tex>. Следовательно, при <tex>\ell>1</tex> мы имеем <tex>B_{j}[\ell]=1</tex> тогда и только тогда, когда существует как минимум одна <tex>j</tex>-активная позиция в диапазоне <tex>R_{j}^{\ell}=[j-|S_{j}^{\ell}|+1,\ j-|S_{j}^{\ell-1}|]</tex>. Положим <tex>R_{j}^{1}=[j,\ j]</tex>, тогда это равенство также сохраняется для <tex>\ell=1</tex> (поскольку <tex>j</tex> всегда <tex>j</tex>-активна) '''''Пример (12):''''' Если <tex>T[1 \ldots 8]=dcccabab</tex>, то 8-активными позициями будут <tex>1,\ 2,\ 3,\ 4,\ 6,\ 8.</tex> Алгоритм построения перебирает <tex>j</tex> от <tex>1</tex> до <tex>n</tex>, сохраняя список активных позиций и вычисляя битовые вектора <tex>B_{j}</tex>. Мы также сохраняем диапазоны <tex>R_{j}^{\ell}</tex> для выбора канонических подстрок, описанных [[#Построение искомой структуры данных|здесь]], которые образуют разбиение <tex>[1,\ j]</tex>. Два следующих результата описывают изменения списка <tex>j</tex>-активных позиций и диапазонов <tex>R_{j}^{\ell}</tex>, когда мы увеличиваем <tex>j</tex>. {{Лемма|id=lemma|author=13|statement= Если список всех <tex>(j-1)</tex>-активных позиций состоит из <tex>p_{1}<p_{2}<</tex> . . . <tex><p_{k}</tex>, то список <tex>j</tex>-активных позиций может быть создан путём добавления <tex>j</tex>, и повторения следующей процедуры: если <tex>p_{\ell}</tex> и <tex>p_{\ell+1}</tex> {{---}} два соседа в текущем списке и <tex>T[j]\neq T[j+p_{\ell}-p_{\ell+1}]</tex>, удаляем <tex>p_{\ell}</tex> или <tex>p_{\ell+1}</tex> из списка, зависимо от того, что <tex>T[j]>T[j+p_{\ell}-p_{\ell+1}]</tex> или <tex>T[j]<T[j+p_{\ell}-p_{\ell+1}]</tex>, соответственно. |proof= Сначала мы докажем, что если позиция <tex>1\leqslant p\leqslant j-1</tex> не является <tex>(j-1)</tex>-активной, то она также не является и <tex>j</tex>-активной. Действительно, если <tex>p</tex> не <tex>(j-1)</tex>-активна, тогда по определению существует позиция <tex>p<p'\leqslant j-1</tex>, такая, что <tex>T[p \ldots j-1]\prec T[p' \ldots j-1]</tex>. Следовательно, <tex>T[p \ldots j]=T[p \ldots j-1]T[j]\prec T[p' \ldots j-1]T[j]=T[p' \ldots j]</tex> и <tex>p</tex> не является <tex>j</tex>-активной. Отсюда, единственными кандидатами на <tex>j</tex>-активные позиции остаются <tex>(j-1)</tex>-активные позиции и <tex>j</tex>. Далее, заметим, что если <tex>1\leqslant p\leqslant j-1</tex> {{---}} <tex>\mathrm{a}(j-1)</tex>-активная позиция и <tex>T[p' \ldots j-1]</tex> {{---}} префикс <tex>T[p \ldots j-1]</tex>, то <tex>p'</tex> тоже является <tex>(j-1)</tex>-активной. Если это не так, тогда существует позиция <tex>p'',\ p'<p''<j-1</tex>, такая, что <tex>T[p' \ldots j-1]\prec T[p'' \ldots j-1]</tex>, и из этого следует, что <tex>T[p \ldots j-1]=T[p' \ldots j-1]T[j+p-p' \ldots j-1]\prec T[p'' \ldots j-1]</tex>, противоречие. <tex>\mathrm{A}(j-1)</tex>-активная позиция <tex>p</tex> не является <tex>j</tex>-активной только если (1) <tex>T[j]\geqslant T[p]</tex> или (2) существует <tex>p<p'\leqslant j-1</tex> такая, что <tex>T[p' \ldots j-1]</tex> {{---}} префикс <tex>T[p \ldots j-1]</tex>, т.е. <tex>p'</tex> {{---}} <tex>(j-1)</tex>-активна и <tex>T[p' \ldots j]\succ T[p \ldots j]</tex> или, другими словами, <tex>T[j]>T[j+p-p']</tex>. Оба этих случая выявляются процедурой удаления.}} '''''Пример (14):''''' Если <tex>T[1 \ldots 9]=dcccababb</tex>, то 8-активными позициями будут: <tex>1,\ 2,\ 3,\ 4,\ 6,\ 8,</tex> и 9-активными позициями будут: <tex>1,\ 2,\ 3,\ 4,\ 8,\ 9,</tex> т.е. мы добавляем <tex>9</tex> в наш список 8-активных позиций, а затем удаляем <tex>6</tex>. {{Утверждение|author=15|statement= Пусть <tex>j\in[1,\ n]</tex> и предположим, что <tex>2^{k}</tex> {{---}} максимальная степень двойки, которой кратно <tex>j</tex>. <tex>(a)</tex> Если <tex>\ell=1</tex>, то <tex>R_{j}^{\ell}=[j,\ j]</tex>. <tex>(b)</tex> Если <tex>2\leqslant\ell<2k+4</tex>, то <tex>R_{j}^{\ell}=R_{j-1}^{\ell-1}</tex>. <tex>(c)</tex> Если <tex>\ell=2k+4</tex>, то <tex>R_{j}^{\ell}=R_{j-1}^{\ell}\cup R_{j-1}^{\ell-1}</tex>. <tex>(d)</tex> Если <tex>\ell>2k+4</tex>, то <tex>R_{j}^{\ell}=R_{j-1}^{\ell}</tex>. |proof= Заметим, что у нас есть <tex>R_{j}^{1}=[j,\ j]</tex> и <tex>R_{j}^{2}=[j-1,\ j-1]</tex>, в то время как для <tex>\ell>2</tex>  <tex>\ell>2 R_{j}^{\ell}=\left\{\begin{array}{ll}[2^{m}(\lfloor\frac{j}{2^{m}}\rfloor-2)+1,\ 2^{m-1}(\lfloor\frac{j}{2^{m-1}}\rfloor-3)] & \mathrm{i}\mathrm{f}\ \ell\ \mathrm{i}\mathrm{s}\ \mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n},\\{[}2^{m}(\lfloor\frac{j}{2^{m}}\rfloor-3)+1,\ 2^{m}(\lfloor\frac{j}{2^{m}}\rfloor-2)] & \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e},\end{array}\right.</tex> где <tex>m=\lfloor\ell/2\rfloor-1</tex>. Также заметим, что <tex>2^{m}(\displaystyle \lfloor\frac{j}{2^{m}}\rfloor-3)=\left\{\begin{array}{l}2^{m}(\lfloor\frac{j-1}{2^{m}}\rfloor-2)\ \mathrm{i}\mathrm{f}\ 2^{m}|j\\2^{m}(\lfloor\frac{j-1}{2^{m}}\rfloor-3)\ \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e},\end{array}\right.</tex> <tex>2^{m}(\displaystyle \lfloor\frac{j}{2^{m}}\rfloor-2)=\left\{\begin{array}{ll}2^{m-1}(\lfloor\frac{j-1}{2^{m-1}}\rfloor-3) & \mathrm{i}\mathrm{f}\ 2^{m}|j\\2^{m}(\lfloor\frac{j-1}{2^{m}}\rfloor-2) & \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}.\end{array}\right.</tex> Более того, <tex>2^{m}|j\Leftrightarrow\ell\leqslant 2k+3</tex> и <tex>2^{m-1}|j\Leftrightarrow\ell\leqslant 2k+5</tex>, что упрощает проверку заявленных формул. Заметим, что возможно, что <tex>R_{j}^{\ell}</tex> определено только для значений <tex>\ell</tex>, меньших, чем <tex>2k+4</tex>. Это именно тот случай, когда число диапазонов растёт на единицу, иначе оно остается неизменным.}}[[Файл:image002.png|Рис. 2|800px]] '''Рис. 2''' Разбиения <tex>[1,\ j]</tex> на <tex>R_{j}^{\ell}</tex> при <tex>j=27</tex> и <tex>j=28</tex>. При <tex>j=28</tex>, <tex>k=2</tex> и <tex>2k+4=8,\ R_{27}^{7}</tex> и <tex>R_{27}^{8}</tex> объединяются в <tex>R_{28}^{8}</tex>. На самом деле, все длины <tex>|R_{j}^{\ell}|</tex> являются степенями двойки, но наш алгоритм не использует это наблюдение.  Мы просматриваем позиции строки <tex>T</tex> слева направо, вычисляя битовые вектора. Мы сохраняем список активных позиций и разбиение <tex>[1,\ j]</tex> на диапазоны <tex>R_{j}^{\ell}</tex>. Кроме того, для каждого диапазона мы храним счетчик, число внутренних активных позиций. Напомним, что <tex>B_{j}[\ell]=1</tex> только когда <tex>l</tex>-й счетчик не равен нулю. Чтобы эффективно обновить список <tex>(j-1)</tex>-активных позиций и получить список <tex>j</tex>-активных позиций, мы также храним для каждого <tex>j'</tex> список указателей на пары соседних позиций, таких, что одна из них должна быть удалена, когда мы достигнем <tex>j=j'</tex>. Всякий раз когда появляется новая пара соседних позиций <tex>p_{z},\ p_{z+1}</tex>, мы считаем <tex>L=</tex> <tex>lcp</tex> <tex>(T[p_{z} \ldots],\ T[p_{z+1} \ldots])</tex> и с этого момента наименьший <tex>j'=p_{z}+L</tex>, когда одна из них должна быть удалена из списка, и вставляем указатель на пару <tex>p_{z},\ p_{z+1}</tex> в <tex>j'</tex>-й список. Когда мы действительно достигнем <tex>j=j'</tex>, мы проследуем по указателю и проверим, что <tex>p_{\ell}</tex> и <tex>p_{\ell+1}</tex> по-прежнему являются соседями. Если это так, мы удаляем соответствующую позицию из списка активных позиций. Иначе мы ничего не делаем. Из леммы 13 следует, что два возможных обновления списка при переходе от <tex>j-1</tex> к <tex>j</tex> добавляют <tex>j</tex> или удаляют какую-то позицию из списка. Это гарантирует, что процесс удаления из леммы 13 и процесс, который мы описали, эквивалентны. Предположим, что мы уже знаем список <tex>(j-1)</tex>-активных позиций, битовый вектор <tex>B_{j-1}</tex>, и число <tex>(j-1)</tex>-активных позиций в каждом диапазоне <tex>R_{j-1}^{\ell}</tex>. Сначала мы обновим список <tex>(j-1)</tex>-активных позиций. Когда позиция удалена из списка, мы находим диапазон, к которому она принадлежит и уменьшаем его счетчик внутренних позиций. Если счетчик становится нулевым, мы очищаем соответствующий бит битового вектора. Далее мы начинаем обновлять разбиение: сначала мы добавляем новый диапазон <tex>[j,\ j]</tex> к разбиению <tex>[1 \ldots j-1]</tex> и инициализируем счетчик активных позиций единицей. Затем, мы обновлям первые <tex>2k+4</tex> диапазонов (<tex>k</tex> {{---}} максимальная степень <tex>2</tex>, которой кратно <tex>j</tex>), используя теорему 15, а также счетчики и битовый вектор. Этот процесс займет <tex>\mathcal{O}(k)</tex> времени, что амортизированно составляет <tex>\displaystyle \mathcal{O}(\sum_{k=1}^{\infty}\frac{k}{2^{k}})=\mathcal{O}(1)</tex> при всех значениях <tex>j</tex>. '''Из вышеописанного следует теорема:'''{{Теорема|id=theorem|author=16|statement= Строка <tex>T</tex> длины <tex>n</tex> может храниться в структуре данных памяти <tex>\mathcal{O}(n)</tex>, которая позволяет вычислять максимальный суффикс любой подстроки <tex>T</tex> за <tex>\mathcal{O}(1)</tex> времени. Данную структуру данных можно построить за <tex>\mathcal{O}(n)</tex> времени.}} ==См. также==* [[Алгоритм Крочемора]]* [[Суффиксный массив]]* [[Алгоритм цифровой сортировки суффиксов циклической строки]] ==Примечания==<references/>==Источники информации==*[[wikipedia:Lyndon word | Lyndon word Wikipedia {{---}} WikipediaLyndon word ]]