Изменения

Если оказалось, что <tex>lcp(i_1,i_2) = N</tex>, то строки равны. Если же <tex>lcp(i_1,i_2) < N</tex>, то символы <tex>s[i_1 + lcp]</tex> и <tex>s[i_2+lcp]</tex> точно различаются, их сравнение позволяет сделать вывод, какой из циклических сдвигов меньше в лексикографическом порядке. И так Итак двоичный поиск работает за <tex>O(\log(N))</tex> остальные операции требуют константного времени, получаем оценку времени, необходимого на сравнение двух циклических сдвигов <tex>O(\log(N))</tex>.