Изменения

|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>. Тогда получаем:

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

Для данных индексов <tex>i<j</tex> будем обозначать как <tex>Suf[i,j]</tex> массив <tex>\{T[i\ldots], \ldots , T[j\ldots]\}</tex> - подмассив с индекса <tex>i</tex> по <tex>j</tex> массива всех суффиксов строки. Множество всех непустых суффиксов строки <tex>Suf[1,|T|]</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> найти [http://en[Алгоритм Касаи и др.wikipedia.org/wiki/LCP_array | наибольший общий префикс]] <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</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\leqslant i<j\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>

|statement= Минимальный суффикс <tex>T[i..\ldots j]</tex> равен либо

<tex>(a)\ T[p..\ldots j]</tex>, где <tex>p</tex> {{---}} начальная позиция минимального суффикса в <tex>Suf[i,j]</tex>, либо

|proof= По Лемме 1 из <ref name="ref1">[[http://link.springer.com/chapter/10.1007/978-3-642-38905-4_5#page-1 | On Minimal and Maximal Suffixes of a Substring]]</ref> лемме 0 минимальный суффикс равен либо <tex>T[p..\ldots j]</tex>, либо его кратчайшему непустому бордеру. Более того, в последнем случае длина минимального суффикса равна не превышает <tex>\displaystyle \frac{1}{2}|T[p..\ldots j]|\leqslant\frac{1}{2}|T[i..\ldots j]|</tex>. С другой стороны, по второму свойству канонических подстрок, длина <tex>S_{j}^{\alpha(i,j)}</tex> равна как минимум <tex>\displaystyle \frac{1}{2}|T[i..\ldots j]|</tex>. Таким образом, во втором случае минимальный суффикс <tex>T[i..\ldots j]</tex> является минимальным суффиксом <tex>S_{j}^{\alpha(i,j)}</tex>. Заметим, что для <tex>i=j</tex> значения <tex>\alpha(i,\ j)</tex> не определены, но тогда выполняется случай <tex>(a)</tex> из условия леммы. Чтобы доказать финальное выражение, вспомним, что нахождение минимального суффикса <tex>Suf [i,\ j]</tex> {{---}} одна из базовых операций, поддерживаемых улучшенным суфмассивом.

Предположим, что мы ищем минимальный суффикс <tex>T[i..\ldots j]</tex> c <tex>\alpha(i,\ j)=\ell</tex>. Наш подход основан на Лемме лемме 1. Если выполняется случай <tex>(a)</tex>, лемма позволяет нам вычислить ответ за <tex>\mathcal{O}(1)</tex>. В общем случае, мы найдём минимальный суффикс <tex>S_{j}^{\ell}</tex>, сравним его с <tex>T[p..\ldots j]</tex> и вернём меньший из них.

Мы используем Лемму лемму 1 и битовый вектор <tex>B_{j}</tex> чтобы посчитать минимальный суффикс <tex>S_{j}^{\ell}</tex>. Назовём <tex>\ell'</tex> наибольший индекс, не превышающий <tex>\ell</tex>, такой, что <tex>B_{j}[\ell']=1</tex>. Заметим, что такой индекс всегда существует (поскольку<tex> B_{j}[1]=1</tex>) и может быть найден за константное время с использованием битовых операций. Для любого индекса <tex>\ell''\in\{\ell'+1,\ \ldots,\ \ell\}</tex> мы имеем <tex>B_{j}[\ell'']=0</tex>, т.е., случай <tex>(b)</tex> Леммы леммы 1 выполняется для <tex>S_{j}^{\ell''}</tex>. Тогда, по индукции, минимальный суффикс <tex>S_{j}^{\ell}</tex> на самом деле является минимальным суффиксом <tex>S_{j}^{\ell'}</tex>. С другой стороны, <tex>B_{j}[\ell']=1</tex>, поэтому для последнего мы можем гарантировать, что выполняется первый случай леммы, что позволяет нам найти минимальный суффикс <tex>S_{j}^{\ell}</tex> за константное время.

Простой алгоритм построения с временем работы <tex>\mathcal{O}(n\log n)</tex> также основывается на Лемме лемме 1. Покажем, что построив улучшенный суфмассив, мы можем найти <tex>B_{j}</tex> за <tex>\mathcal{O}(\log n)</tex>. Мы ищем минимальный суффикс <tex>S_{j}^{\ell}</tex> для последовательных значений <tex>\ell</tex>. Как только мы получили результат <tex>\ell-1</tex>, случай <tex>(a)</tex> Леммы леммы 1 даёт нам второго кандидата на минимальный суффикс <tex>S_{j}^{\ell}</tex>, и наш улучшенный суфмассив позволяет нам выбрать наименьшего из этих двух кандидатов. Мы устанавливаем <tex>B_{j}[\ell]=1</tex> если меньший кандидат не содержится в <tex>S_{j}^{\ell-1}</tex>. Стало быть, мы получили следующий результат:

Для <tex>\ell=1</tex> мы определим <tex>S_{j}^{1}=T[j..\ldots j]</tex>. Для <tex>\ell>1</tex> установим <tex>m=\lfloor\ell/2\rfloor-1</tex> и определим <tex>S_{j}^{\ell}</tex> таким образом:

Заметим, что если <tex>2 \cdot 2^{m}\leqslant j<3\cdot 2^{m}</tex>, то <tex>T[1..\ldots j]=S_{j}^{2m+2}</tex>, в то время как, если <tex>3 \cdot 2^{m}\leqslant j<4\cdot 2^{m}</tex>, то <tex>T[1..\ldots j]=S_{j}^{2m+3}</tex>. Очевидно, что количество таких подстрок, заканчивающихся в <tex>j</tex> получается <tex>\mathcal{O}(\log n)</tex>. Докажем далее, что канонические подстроки, выбранные вышеуказанным способом, имеют необходимые свойства.

|proof= Положим <tex> m=\lfloor\log|T[i..\ldots j]|\rfloor</tex>. Заметим, что

<tex>|S_{j}^{2m-1}|=3\cdot 2^{m-2}+(j \ mod \ 2^{m-2})<2^{m}\leqslant|T[i..\ldots j]|</tex>

<tex>|S_{j}^{2m+2}|=2\cdot 2^{m}+(j \ mod \ 2^{m})\geqslant 2^{m+1}>|T[i..\ldots j]|</tex>.

После построения улучшенного суфмассива, мы установили все биты<tex>B_{j}[1]</tex> в 1. После этого, для каждого <tex>\ell>1</tex> мы посчитали минимальные суффиксы подстрок <tex>S_{j}^{\ell}</tex>, как указано далее. Зафиксируем <tex>\ell>1</tex> и разобьём <tex>T</tex> на куски размером <tex>2^{m}</tex>(где <tex>m=\lfloor\ell/2\rfloor-1</tex>) . Теперь каждый <tex>S_{j}^{\ell}</tex> является префиксом конкатенации максимум 4х таких кусков. ВспомнимИзвестно, что по данной строке можно посчитать длины минимальных суффиксов всех её префиксов за линейное время с помощью одной из вариаций алгоритма Дюваля (Алгоритм 3.1 в <ref name="ref2">[[http://wwwge.sciencedirect.comtt/api/1/sciencefiles/article5uKJjWQ/pii0/0196677483900172 | blob?download Factorizing words over an ordered alphabet]]</ref>). Разделим <tex>T</tex> на куски длиной <tex>2^{m}</tex>(где <tex>m=\lfloor\ell/2\rfloor-1</tex>) и запустим этот алгоритм для каждых четырёх (или менее, в конце) последовательных кусков. Это даст нам минимальные суффиксы <tex>S_{j}^{\ell}</tex> для всех <tex>1\leqslant j\leqslant n</tex>, за время <tex>\mathcal{O}(n)</tex>. Значение <tex>B_{j}[\ell]</tex> определено с помощью сравнения длины вычисленного минимального суффикса <tex>S_{j}^{\ell}</tex> с <tex>|S_{j}^{\ell-1}|</tex>. У нас <tex>\mathcal{O}(\log n)</tex> фаз алгоритма, что даёт нам время <tex>\mathcal{O}(n\log n)</tex> и <tex>\mathcal{O}(n)</tex> требуемой памяти.

Как и ранее, предположим, что мы ищем минимальный суффикс <tex>T[i..\ldots j]</tex>, при <tex>\alpha(i,\ j)=\ell</tex>. Самое сложное в этом {{---}} найти минимальный суффикс <tex>S_{j}^{\ell}</tex>, и далее необходимо найти <tex>\ell'\leqslant\ell</tex>, такой, что минимальный суффикс <tex>S_{j}^{\ell}</tex> на самом деле является минимальным суффиксом <tex>S_{j}^{\ell'}</tex>, но длиннее, чем <tex>|S_{j}^{\ell'-1}|</tex>. Если <tex>\ell=\tau k</tex> для целого <tex>k</tex>, мы можем найти наибольший <tex>k'\leqslant k</tex>, такой, что <tex>B[k']=1</tex>, и нам будет известно, что <tex>\ell'\in(\tau(k'-1),\ \tau k']</tex>. В общем случае, мы выберем наибольший <tex>k</tex>, такой что <tex>\tau k\leqslant\ell</tex>, и будем знать, что мы должны рассмотреть <tex>\ell'\in(\tau k,\ \ell]</tex> и <tex> \ell'\in(\tau(k'-1),\ \tau k']</tex>, где <tex>k'</tex> определён, как в предыдущем случае. В результате, мы имеем <tex>\mathcal{O}(\tau)</tex> возможных значений <tex>\ell'</tex>, и нам известно, что искомый суффикс может быть найден, используя случай <tex>(a)</tex> Леммы леммы 1 для <tex>S_{j}^{\ell'}</tex> для каждого из этих значений. Тогда мы просто сгенерируем всех этих кандидатов и используем улучшенный суфмассив, чтобы найти наименьший суффикс среди них. В результате, запрос к нашей структуре данных будет выполняться за <tex>\mathcal{O}(\tau)</tex>. 

Для любого <tex>1\leqslant\tau\leqslant\log n</tex>, строка <tex>T</tex> длиной <tex>n</tex> может храниться в структуре данных, занимающей <tex>\mathcal{O}(n)</tex> памяти, позволяющей вычислять минимальный суффикс любой из подстрок <tex>T</tex> за время <tex>\mathcal{O}(\tau)</tex>. Такая структура данных может быть построена за <tex>\mathcal{O}(n\log {n/\tau})</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[\mu..\ldots j]</tex> строки <tex>T[i..\ldots j]</tex> равен либо

<tex>(a) T[p..\ldots j]</tex>, либо

Алгоритмы построения за <tex>\mathcal{O}(n\log n)</tex> и компромисс между временем запросов и временем построения, описанные [[#Построение искомой структуры данных|здесь]] и [[#Компромисс|здесь]] соответственно, также легко адаптируются к нашей задаче. В случае поиска максимального суффикса, тем не менее, мы можем добиться времени построения <tex>\mathcal{O}(n)</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 в [http://link.springer.com/chapter/10.1007/978-3-642-38905-4_5#page-1 6]

|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 из [http:<ref name="ref1" //link.springer.com/chapter/10.1007/978-3-642-38905-4_5#page-1 6]>, но здесь мы приводим доказательства вследствие другого обозначения.

|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>

|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 7M. Crochemore, C. Hancart, and T. Lecroq. Algorithms on Strings. Cambridge University Press, 2007]</ref>.

Таким образом, <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>.

Пусть <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>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>[</tex>1, <tex>\ j]</tex>. Два следующих результата описывают изменения списка <tex>j</tex>-активных позиций и диапазонов <tex>R_{j}^{\ell}</tex>, когда мы увеличиваем <tex>j</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>.

Мы просматриваем позиции строки <tex>T</tex> слева направо, вычисляя битовые вектора. Мы сохраняем список активных позиций и разбиение <tex>[</tex>1, <tex>\ 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> по-прежнему являются соседями. Если это так, мы удаляем соответствующую позицию из списка активных позиций. Иначе мы ничего не делаем.

Предположим, что мы уже знаем список <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> времени, что амортизированно составляет