Наименьший циклический сдвиг строки

Дана строка s. Среди всех её циклических сдвигов (поворотов) верните лексикографически наименьший. Например, для "bca" сдвиги - "bca", "cab", "abc"; ответ - "abc". Перебор всех n сдвигов с посимвольным сравнением - O(n^2). Существует алгоритм Бута, находящий ответ за O(n).