Изменения

|proof= Точно так же, как и структура, описанная в части о минимальном суффиксе, наша структура данных, не считая улучшенныйсуффиксный массив, содержит битовые вектора <tex>B_{j},\ j\in[1,\ n]</tex>, с <tex>B_{j}[\ell]=1</tex>, если <tex>\ell=1</tex> или максимальный суффикс строки <tex>S_{j}^{\ell}</tex> длиннее <tex>|S_{j}^{\ell-1}|</tex>. Алгоритм запроса, описанный в части 4.1,очевидно, может быть адаптирован к нашей задаче, только вместо Леммы 1 мы будем использовать Лемму 7 и выбирать наибольшего из двух кандидатов в качестве ответа. Это демонстрирует следующая теорема:

Мы начнем со вспомогательной леммы, которая обозначалась как Лемма 2 в [http://link.springer.com/chapter/10.1007/978-3-642-38905-4_5#page-1 16]

|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 16], но здесь мы приводим доказательства вследствие другого обозначения.

|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 47].