J. Наименьший поворот

Среди всех циклических сдвигов строки найдите лексикографически наименьший. Выведите позицию, с которой он начинается.

Наивно - квадрат

Сравнить все $n$ поворотов попарно стоит $O(n^2)$. При $n = 10^6$ это не проходит, нужен линейный алгоритм.

Алгоритм Дюваля: разложение Линдона

Строка проста по Линдону, если она строго меньше всех своих собственных суффиксов. Любая строка единственным образом раскладывается в невозрастающую последовательность простых слов, и это разложение строится за $O(n)$ тремя указателями.

Наименьший поворот - это начало последнего простого слова в разложении удвоенной строки:

std::string t = s + s;
int i = 0, best = 0;
while (i < n) {
    best = i;
    int j = i + 1, k = i;
    while (j < 2 * n && t[k] <= t[j]) {
        k = (t[k] < t[j]) ? i : k + 1;
        j++;
    }
    while (i <= k) i += j - k;
}

Проще, но не всегда

Есть более простой приём: посчитать Z-функцию или префикс-функцию удвоенной строки и найти минимум сравнением по одному символу за раз. Он тоже линейный, но требует аккуратности с границами; Дюваль короче и не использует дополнительной памяти.

Одинаковые повороты

У строки aaaa все повороты равны. В таком случае в ответе нужна наименьшая позиция - алгоритм Дюваля даёт именно её, потому что при равенстве символов указатель $k$ движется вперёд, а не сбрасывается.

Подробнее: «Нормализация строк».

Одна строка из строчных латинских букв длиной не больше $10^6$.

Выведите наименьшую позицию (нумерация с нуля), с которой начинается лексикографически наименьший циклический сдвиг.