Лексикографически первая подстрока фиксированного размера для каждой позиции скользящего окна

Question

Из данной строки я хочу найти подстроку (некоторый фиксированный размер k), которая идет первой в лексикографическом порядке сортировки среди всех подстрок одинакового размера в строке.

Я бы сделал это с помощью скользящего окна над очень длинной строкой (размер m) и хотел бы найти эту подстроку для каждой позиции скользящего окна (размер n> k), когда я перемещаю ее через строку.

Кажется, что тривиальное решение заняло бы время m * O (n log (n)).

Я думаю, что мог бы добраться до m * O (log (n)), если бы я сделал нормальную сортировку в начале, а затем просто удалил подстроку, которая начинается в начале последней позиции окна, и вставил новую подстроку, которая заканчивается в конце текущей позиции окна в уже отсортированную коллекцию подстрок каждый раз, когда я перемещаю окно. (разумеется, я не храню подстроки отдельно, а просто сохраняю их позиции в коллекции, поэтому пространство должно быть n-k целых чисел),

Есть ли более быстрый алгоритм для этого?

Answer 1

Пусть m будет размером входной строки, а n будет длиной искомой строки. Я думаю, что вы можете решить эту проблему за время O (m), используя суффиксные деревья.

Начните с построения дерева суффиксов для входной строки. Это занимает время O (м). Теперь выполните поиск в дереве по глубине, всегда выбирая лексикографически первый выбор на каждом шаге. При этом первой найденной строкой длины n будет лексикографически первая подстрока длины n. Выполнение DFS над деревом суффиксов для строки длиной m занимает время O (m), поэтому в целом это занимает время O (m).