8
правок
Изменения
Нет описания правки
|statement= Рассмотрим подстроку <tex>T[i..j]</tex>. Используя улучшенный суффиксный массив строки <tex>T</tex>, за <tex>\mathcal{O}(1)</tex> можно найти индекс <tex>p(i\leq p\leq j)</tex> такой, что максимальный суффикс <tex>T[\mu..j]</tex> строки <tex>T[i..j]</tex> равен либо
<tex>(a)T[p..j]</tex>, либо
<tex>(b)</tex> максимальный суффикс строки <tex>S_{j}^{\alpha(i,j)}</tex>
|proof=
Алгоритмы построения за <tex>\mathcal{O}(n\log n)</tex> и компромисс между временем запросов и временем построения, описанные в секциях 4.2 и 4.3, также легко адаптируются к нашей задаче. В случае поиска максимального суффикса, тем не менее, мы можем добиться времени построения <tex>\mathcal{O}(n)</tex>, как будет показано в секции 5.2.
}}
===Доказательство леммы 7===
Ниже мы описываем алгоритм, работающий за константное время, который возвращает позицию <tex>p\in[i,\ j]</tex>.
Мы начнем со вспомогательной леммы, которая обозначалась как Лемма 2 в [http://link.springer.com/chapter/10.1007/978-3-642-38905-4_5#page-1 1]
{{Лемма
|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} \ 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 1], но здесь мы приводим доказательства вследствие другого обозначения.
}}
{{Лемма
|id=lemma
|author=10
|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>.
Предположим, что <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\leq\ell\leq 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 2</tex>, потому что <tex>2|P_{1}|\geq|P_{2}|=|P_{1}|+|\rho|</tex>, поэтому <tex>|P_{1}|\geq|\rho|.\ </tex>
}}
{{Лемма
|id=lemma
|author=11
|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 4].
[[Файл:image001.png|Рис. 1. Схематичная иллюстрация к Лемме 11.|800px]]
Таким образом, <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>.
}}
'''Доказательство леммы 7'''
<tex>\triangleright</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>\triangleleft</tex>
*[http://books.google.ru/books?id=Q5K3vREGVhAC&printsec=frontcover#v=onepage&q&f=false Algebras, Rings, and Modules: Lie Algebras and Hopf Algebras", Michiel Hazewinkel, Nadezhda Mikhaĭlovna Gubareni, Vladimir V. Kirichenko, страница 242]
*[http://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=5&ved=0CF0QFjAE&url=http%3A%2F%2Fmimuw.edu.pl%2F~kociumaka%2Ffiles%2Fcpm2014a_draft.pdf&ei=__CIU_7gLYap4gTw7YDACA&usg=AFQjCNG-fcqnjok7hpyiO8niGTFTSOgBJQ&sig2=Ku2k8vAz4QJHolkr_BOLyQ&bvm=bv.67720277,d.bGE&cad=rjt Computing minimal and maximal suffixes of a substring revisited]
*[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]
*[http://link.springer.com/chapter/10.1007/978-3-642-38905-4_5#page-1 On Minimal and Maximal Suffixes of a Substring]
*[http://www.sciencedirect.com/science/article/pii/0196677483900172 Factorizing words over an ordered alphabet]
