Изменения

Данный алгоритм работает за <tex>O(N \cdot M)</tex>, где <tex>M</tex> {{---}} размер алфавита, <tex>N</tex> {{---}} длина строки, что не очень быстро. Этот алгоритм можно реализовать за <tex>O(N\log M)</tex>.

Для решения будем использовать [[Декартово_дерево | декартово дерево]].