Изменения

Заметим, что если <tex>2 \cdot 2^{m}\leq j<3\cdot 2^{m}</tex>, то <tex>T[1..j]=S_{j}^{2m+2}</tex>, в то время как, если <tex>3 \cdot 2^{m}\leq j<4\cdot 2^{m}</tex>, то <tex>T[1..j]=S_{j}^{2m+3}</tex>. Очевидно, что количество таких подстрок, заканчивающихся в <tex>j</tex> получается <tex>\mathcal{O}(\log n)</tex>. Докажем далее, что канонические подстроки, выбранные вышеуказанным способом, имеют необходимые свойства.

|author=3

|statement=

}}

|author=4

|statement= Для <tex>1\leq i<j\leq n</tex>, величина <tex>\alpha(i,\ j)</tex> может быть посчитана за константное время.