Изменения
→Алгоритм за O(N log^2(N)) (префиксы циклических сдвигов)
После шага <tex>l =2^{\lceil log_2(n)\rceil} \ge N</tex>. Все циклические сдвиги будут отсортированы. Всего шагов <tex>O(log(N))</tex>, каждый шаг проводится за <tex>O(N log(n))</tex>, итоговая асимптотика <tex>O(N log^2(N))</tex>.
=== Псевдокод ===
'''suf_array'''(s)
suf <tex>\leftarrow \{0, 1, \dots, |s|\}</tex>
'''sort''' (suf, '''compare1''')
<tex>c \leftarrow \{</tex>s[0], s[1], ..., s[|s| - 1]<tex>\}</tex>
'''for''' <tex>l</tex> = 1 '''to''' <tex>2^{\lceil log_2(n)\rceil - 1}</tex> '''step''' <tex>l \leftarrow 2l</tex> '''do'''
'''sort''' (suf, '''compare2''')
<tex>c'</tex>[suf[0]] <tex>\leftarrow</tex> 0
'''for''' <tex>i</tex> = 1 '''to''' <tex>|s|-1</tex> '''do'''
<tex>l_1 \leftarrow c</tex>[suf[<tex>i - 1</tex>]]
<tex>r_1 \leftarrow c</tex>[suf[<tex>i - 1</tex>] + <tex>l</tex>]
<tex>l_2 \leftarrow c</tex>[suf[<tex>i</tex>]]
<tex>r_2 \leftarrow c</tex>[suf[<tex>i</tex>] + <tex>l</tex>]
'''if''' (<tex>c</tex>[<tex>l_1</tex>] <tex>\neq</tex> <tex>c</tex>[<tex>l_2</tex>] '''or''' <tex>c</tex>[<tex>r_1</tex>] <tex>\neq</tex> <tex>c</tex>[<tex>r_2</tex>])
<tex>c'</tex>[suf[<tex>i</tex>]] = <tex>c'</tex>[suf[<tex>i - 1</tex> + 1]]
'''else'''
<tex>c'</tex>[suf[<tex>i</tex>]] = <tex>c'</tex>[suf[<tex>i - 1</tex>]]
<tex>c \leftarrow c'</tex>
'''ret''' suf
'''compare1''' (<tex>j_1</tex>, <tex>j_2</tex>)
'''ret''' s[<tex>j_1</tex> + same] - s[<tex>j_2</tex> + same]
'''compare2''' (<tex>j_1</tex>, <tex>j_2</tex>)
'''if''' (<tex>c</tex>[<tex>j_1</tex>] \neq <tex>c</tex>_[<tex>j_2</tex>])
'''ret''' <tex>c</tex>[<tex>j_1</tex>] - <tex>c</tex>[<tex>j_2</tex>]
'''else'''
'''ret''' <tex>c</tex>[<tex>j_1 + l</tex>] - <tex>c</tex>[<tex>j_2 + l</tex>]
