У меня есть какая-то строка и я строю ее суффиксный массив
Всегда ли первый элемент суффиксного массива совпадает с позицией наименьшего циклического сдвига строки?
Stack Overflow на русском — это сайт вопросов и ответов для программистов. Присоединяйтесь! Регистрация займёт не больше минуты.
Присоединиться к сообществуДа, всё верно, первый элемент указывает на позицию наименьшего циклического сдвига.
Один из методов построения СМ как раз сортирует циклические сдвиги строки (со вставкой спецсимвола)
см. "применения" здесь