Изменения

|statement= Рассмотрим подстроку <tex>T[i..j]</tex>. Используя улучшенный суффиксный массив строки <tex>T</tex>, за <tex>\mathcal{O}(1)</tex> времени можно найти такой индекс <tex>p(i\leq leqslant p\leq leqslant j)</tex>, что максимальный суффикс <tex>T[\mu..j]</tex> строки <tex>T[i..j]</tex> равен либо

|proof= Пусть <tex>T[p_{1}..]</tex> {{---}} максимальный суффикс в <tex>Suf [i,\ r]</tex> и <tex>T[p_{2}..]</tex> {{---}} максимальный суффикс в <tex>Suf [i,\ p_{1}-1]</tex>. Очевидно, <tex>P_{1}=T[p_{1}..j]</tex> является префиксом строки <tex>T[\mu..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}|\geqgeqslant|P_{2}|</tex>. Благодаря этому, <tex>P_{1}</tex> и <tex>P_{2}</tex> имеют некоторые интересные свойства, описанные в последующих леммах. Эти леммы по существу повторяют Леммы 4 и 5 из [http://link.springer.com/chapter/10.1007/978-3-642-38905-4_5#page-1 6], но здесь мы приводим доказательства вследствие другого обозначения.

|statement= Подстрока <tex>\rho=T[p_{2}..p_{1}-1]</tex> {{---}} минимальный период строки <tex>P_{2}</tex>, т.е. <tex>\rho</tex> {{---}} кратчайшая строка, такая, что для какого-то <tex>s\geq geqslant 1</tex> выполняется <tex>P_{2}=\rho^{s}\rho'</tex>.|proof= Поскольку <tex>P_{1}</tex> {{---}} бордер <tex>P_{2},\ \rho=T[p_{2}..p_{1}-1]</tex> {{---}} период <tex>P_{2}</tex>. Остается лишь доказать, что невозможно найти более короткий период. Таким образом, рассмотрим(consider) кратчайший период <tex>\gamma</tex>, и предположим, что <tex>|\gamma|<|\rho|</tex>. Тогда <tex>|\gamma|+|\rho|\leq leqslant 2|\rho|\leqleqslant|T[p_{2}..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\geq geqslant 2</tex>.

Предположим, что <tex>T[p_{1}..]\prec\gamma T[p_{1}..]</tex>. Тогда приписывание к обеим частям последнего неравенства степеней <tex>\gamma</tex> даёт <tex>\gamma^{\ell-1}T[p_{1}..]\prec\gamma^{\ell}T[p_{1}..]</tex> для любого <tex>1\leqleqslant\ell\leq leqslant k</tex>, таким образом из транзитивности <tex>\prec</tex> получаем <tex>T[p_{1}..]\prec\gamma^{k}T[p_{1}..]=T[p_{2}..]</tex>, что противоречит максимальности <tex>T[p_{1}..]</tex> in <tex>Suf[i,\ r]</tex>. Таким образом, <tex>T[p_{1}..]\succ\gamma T[p_{1}..]</tex>, и следовательно <tex>\gamma^{k-1}T[p_{1}..]\succ\gamma^{k}T[p_{1}..]</tex>. Но <tex>\gamma^{k-1}T[p_{1}..]=T[p_{2}+|\gamma|..]</tex> и <tex>\gamma^{k}T[p_{1}..]=T[p_{2}..]</tex>, поэтому <tex>T[p_{2}+|\gamma|..]</tex> больше, чем <tex>T[p_{2}..]</tex> и принадлежит <tex>Suf [i,\ p_{1}-1]</tex>, противоречие. Заметим, что на самом деле <tex>s\geq geqslant 2</tex>, потому что <tex>2|P_{1}|\geqgeqslant|P_{2}|=|P_{1}|+|\rho|</tex>, поэтому <tex>|P_{1}|\geqgeqslant|\rho|.\ </tex>

|proof= Очевидно, что <tex>P_{2}</tex> является бордером <tex>T[\mu..j]</tex>. Из <tex>P_{2}=\rho P_{1}</tex> и <tex>|T[\mu..j]|\leq leqslant 2|P_{1}|</tex> имеем <tex>|T[\mu..j]|+|\rho|\leq leqslant 2|P_{1}|+\rho\leq leqslant 2|P_{2}|</tex>. Следовательно вхождения <tex>P_{2}</tex> в качестве префикса и в качестве суффикса строки <tex>T[\mu..j]</tex> перекрывают друг друга как минимум в <tex>|\rho|</tex> позициях. Т.к. <tex>|\rho|</tex> {{---}} период <tex>P_{2}</tex>, отсюда следует, что <tex>|\rho|</tex> также является периодом <tex>T[\mu..j]</tex>. Таким образом, <tex>T[\mu..j]=\rho''\rho^{r}\rho'</tex>, где <tex>r</tex> {{---}} целое число и <tex>\rho''</tex> {{---}} суффикс <tex>\rho</tex>. Более того, <tex>\rho^{2}</tex> {{---}} это префикс <tex>T[\mu..j]</tex>, поскольку является префиксом <tex>P_{2}</tex>, который в свою очередь является префиксом <tex>T[\mu..j]</tex>. Теперь <tex>\rho''\neq\xi j</tex> будет означать нетривиальное вхождение <tex>\rho</tex> в <tex>\rho^{2}</tex>, которое противоречит примитивности <tex>\rho</tex>, смотри [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 7].

Наш алгоритм основывается на следующем понятии. Для <tex>1\leq leqslant p\leq leqslant j\leq leqslant n</tex> мы говорим, что позиция <tex>p</tex> <tex>j</tex>-активна, если не существует такой позиции <tex>p'\in\{p+1,\ \ldots,\ j\}</tex>, что <tex>T[p'..j]\succ T[p..j]</tex>. Другими словами, <tex>p</tex> {{---}} <tex>j</tex>-активна тогда и только тогда, когда <tex>T[p..j]</tex> {{---}} максимальный суффикс самого себя.

|proof= Сначала мы докажем, что если позиция <tex>1\leq leqslant p\leq leqslant j-1</tex> не является <tex>(j-1)</tex>-активной, то она также не является и <tex>j</tex>-активной. Действительно, если <tex>p</tex> не <tex>(j-1)</tex>-активна, тогда по определению существует позиция <tex>p<p'\leq leqslant j-1</tex>, такая, что <tex>T[p..j-1]\prec T[p'..j-1]</tex>. Следовательно, <tex>T[p..j]=T[p..j-1]T[j]\prec T[p'..j-1]T[j]=T[p'..j]</tex> и <tex>p</tex> не является <tex>j</tex>-активной. Отсюда, единственными кандидатами на <tex>j</tex>-активные позиции остаются <tex>(j-1)</tex>-активные позиции и <tex>j</tex>.

Далее, заметим, что если <tex>1\leq leqslant p\leq leqslant j-1</tex> {{---}} <tex>\mathrm{a}(j-1)</tex>-активная позиция и <tex>T[p'..j-1]</tex> {{---}} префикс <tex>T[p..j-1]</tex>, то <tex>p'</tex> тоже является <tex>(j-1)</tex>-активной. Если это не так, тогда существует позиция <tex>p'',\ p'<p''<j-1</tex>, такая, что <tex>T[p'..j-1]\prec T[p''..j-1]</tex>, и из этого следует, что <tex>T[p..j-1]=T[p'..j-1]T[j+p-p'..j-1]\prec T[p''..j-1]</tex>, противоречие. <tex>\mathrm{A}(j-1)</tex>-активная позиция <tex>p</tex> не является <tex>j</tex>-активной только если (1) <tex>T[j]\geq geqslant T[p]</tex> или (2) существует <tex>p<p'\leq leqslant j-1</tex> такая, что <tex>T[p'..j-1]</tex> {{---}} префикс <tex>T[p..j-1]</tex>, т.е. <tex>p'</tex> {{---}} <tex>(j-1)</tex>-активна и <tex>T[p'..j]\succ T[p..j]</tex> или, другими словами, <tex>T[j]>T[j+p-p']</tex>. Оба этих случая выявляются процедурой удаления.

<tex>(b)</tex> Если <tex>2\leqleqslant\ell<2k+4</tex>, то <tex>R_{j}^{\ell}=R_{j-1}^{\ell-1}</tex>.

Более того, <tex>2^{m}|j\Leftrightarrow\ell\leq leqslant 2k+3</tex> и <tex>2^{m-1}|j\Leftrightarrow\ell\leq leqslant 2k+5</tex>, что упрощает проверку заявленных формул. Заметим, что возможно, что <tex>R_{j}^{\ell}</tex> определено только для значений <tex>\ell</tex>, меньших, чем <tex>2k+4</tex>. Это именно тот случай, когда число диапазонов растёт на единицу, иначе оно остается неизменным.