Изменения

Пусть <tex>\sigma</tex> -- перестановка чисел <tex>{0, ..., N}</tex>, удовлетворяющая условию:

и в случае равенства <tex>B_{\sigma(i)}</tex> и <tex>B_{\sigma(i + 1)}</tex> выполнено -- <tex>\sigma(i) < \sigma(i + 1)</tex>. Перестановка однозначно определяется текстом <tex>B</tex> и ее можно посчитать за <tex>O(N)</tex>, используя сортировку подсчетом. Рассмотрим перестановку <tex>\sigma</tex> как отображение <tex>\sigma : {0, ..., N} \to {0, ..., N}</tex>. Пусть <tex>\sigma^{k}</tex> копмозиция <tex>k</tex> отображений <tex>\sigma^{k} = \sigma \circ \sigma \circ ... \circ \sigma</tex>.