Изменения

|statement= Пусть <tex>P_{1}=T[p_{1}..j]</tex> — {{---}} префикс строки <tex>T[\mu..j]</tex> и пусть <tex>P_{2}=T[p_{2}..j]</tex>, где <tex>T[p_{2}..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..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}|\geq|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 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 2|\rho|\leq|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 2</tex>.

|statement= Положим, <tex>P_{2}=\rho P_{1}=\rho^{s}\rho'</tex>. Тогда максимальный суффикс <tex>T[\mu..j]</tex> — {{---}} длиннейший суффикс строки <tex>T[i..j]</tex> равен <tex>\rho^{t}\rho'</tex> для некоторого <tex>t</tex>. (См. рисунок 1)|proof= Очевидно, что <tex>P_{2}</tex> является бордером <tex>T[\mu..j]</tex>. Из <tex>P_{2}=\rho P_{1}</tex> и <tex>|T[\mu..j]|\leq 2|P_{1}|</tex> имеем <tex>|T[\mu..j]|+|\rho|\leq 2|P_{1}|+\rho\leq 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>T[\mu..j]=\rho^{r}\rho'</tex>. Если <tex>t>r</tex>, тогда <tex>\rho^{t}\rho'\succ\rho^{r}\rho'</tex>, поэтому <tex>T[\mu..j]</tex> — {{---}} длиннейший суффикс строки <tex>T[i..j]</tex>, равный <tex>\rho^{t}\rho'</tex> для некоторого <tex>t</tex>.

Пусть <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}</tex> и <tex>p_{2}</tex> за <tex>\mathcal{O}(1)</tex>, используя улучшенный суффиксный массив. Затем проверим, что <tex>T[p_{1}..j]</tex> является префиксом <tex>T[p_{2}..j]</tex>. Если это неверно, то мы возвращаем <tex>p=p_{1}</tex>. Иначе, мы вычисляем максимальное целое число <tex>r</tex>, такое, что <tex>\rho^{r}</tex> (для <tex>\rho=T[p_{2}..p_{1}-1])</tex>) — {{---}} суффикс <tex>T[i..p_{1}-1]</tex>, используя метод из алгоритма поиска минимального суффикса, и возвращаем <tex>p=p_{1}-r|\rho|</tex>. Из вышеописанных лемм следует, что если <tex>T[\mu..j]</tex> длиннее <tex>S_{j}^{\alpha(i,j)}</tex>, тогда <tex> p=\mu</tex>.

Наш алгоритм основывается на следующем понятии. Для <tex>1\leq p\leq j\leq 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> — {{---}} максимальный суффикс самого себя. Максимальный суффикс любой строки является своим собственным максимальным суффиксом, поэтому из определения следует, что стартовая позиция максимального суффикса строки <tex>T[i..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>-активна)

|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>, соответственно.

Далее, заметим, что если <tex>1\leq p\leq 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 T[p]</tex> или (2) существует <tex>p<p'\leq 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>j\in[1,\ n]</tex> и предположим, что <tex>2^{k}</tex> — {{---}} максимальная степень двойки, которой кратно <tex>j</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..j-1]</tex> и инициализируем счетчик активных позиций единицей. Затем, мы обновлям первые <tex>2k+4</tex> диапазонов (<tex>k</tex> — {{---}} максимальная степень 2, которой кратно <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>.