Изменения

|proof= По Лемме 1 из <refname="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> минимальный суффикс равен либо <tex>T[p..j]</tex>, либо его кратчайшему непустому бордеру. Более того, в последнем случае длина минимального суффикса равна не превышает <tex>\displaystyle \frac{1}{2}|T[p..j]|\leqslant\frac{1}{2}|T[i..j]|</tex>. С другой стороны, по второму свойству канонических подстрок, длина <tex>S_{j}^{\alpha(i,j)}</tex> равна как минимум <tex>\displaystyle \frac{1}{2}|T[i..j]|</tex>. Таким образом, во втором случае минимальный суффикс <tex>T[i..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>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 в <refname="ref2">[[http://www.sciencedirect.com/science/article/pii/0196677483900172 | 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> требуемой памяти.