147
правок
Изменения
→Доказательство корректности
===Доказательство корректности===
{| border="1"
|0||а|| ||р||9
|-
|1||а||||д||7
|-
|2||а|| ||a||0
|-
|3||а|| ||к||8
|-
|4||а|| ||р||10
|-
|5||б|| ||a||1
|-
|6||б|| ||a||2
|-
|7||д|| ||a||3
|-
|8||к|| ||a||4
|-
|9||р|| ||б||5
|-
|10||р|| ||б||6
|}
Пусть текст <tex>T</tex> состоит из <tex>N + 1</tex> символов, занумерованных с нуля: <tex>T[0..N]</tex>. Буквы <tex>T[i]</tex> принадлежат некоторому алфавиту <tex>A</tex>. Лексикографический порядок (строгий) на строках из алфавита <tex>A</tex> будем обозначать <tex>\preceq (\prec)</tex>. Обозначим через <tex>S_{k}T</tex> циклический сдвиг текста <tex>T</tex> на <tex>k</tex> символов влево:
:{|
Если лексикографически отсортировать буквы последнего столбца и поместить их в первый столбец, то получится таблица
}}
