Найти K Крупнейшей подстроку

Question

Я даю строку S длиной 10^5, теперь для все возможных N+1C2 подстроки я должен выводить K подстроки, когда все подстроки сортируются в порядке возрастания.

For Ex: 
S= STACK 

Substring: 
    A 
    AC 
    ACK 
    C 
    CK 
    S 
    ST 
    STA ... so on 

My Approach: Сформировать Все Substring сортировать их и вывести K Substring

Тогда я узнал о Suffix массива, для данной строки я сгенерировал массив суффиксов, но как вычислить K элемент с использованием массива суффиксов? Не могли бы вы объяснить, как использовать Suffix Array для вычисления элемента K?

Я создал и понял массив суффикса? Но как его использовать.
Suffix Array Algorithm Used

Answer 1

Дерево суффиксов дает вам все суффиксы строки. Поэтому, если строка является «стеком», самым длинным суффиксом является стек $ (мы добавляем фиктивный дополнительный символ, чтобы любой суффикс был префиксом другого суффикса). Следующий самый длинный - это ключ $, затем ack $. Все это доступно из корня.

Теперь подстрока является только префиксом суффикса. Прогуливаясь по дереву, вы получаете все подстроки, отсортированные. Это одно, довольно дорогое решение. Чтобы сделать поиск более дешевым, скажем, мы хотим, чтобы K = 5. У нас есть суффикс, начинающийся A, и он имеет три пути к символу конца $. Итак, A не является началом нашего суффикса. У нас нет суффикса B, так что это не наш ответ. У нас есть суффикс, начинающийся с C, и он имеет два пути к $. Итак, для k = 5 первая буква суффикса должна быть «C». Затем мы продолжим. Мы потеряли три позиции до a, поэтому нам нужен второй суффикс под первым C-узлом.