Ключ к шифру

Пусть подстрока t является ответом на задачу. Обозначим за t1 и t2 префикс и суффикс t максимальные по длине и не равные t. Обозначим за s1 и s2 суффиксы строки s, префиксами которых являются t1 и t2 соответственно. Тогда t1 и t2 являются наибольшим общим префиксом s1 и s2.

Построим суффиксный массив строки s и посчитаем наибольшие общие префиксы соседних суффиксов в массиве. Отсортируем n - 1 пару по возрастанию lcp. Будем поддерживать отрезки суффиксов в суффиксном массиве с одинаковым префиксом на текущий момент. Очередная пара соседних суффиксов, с минимальной длиной lcp среди оставшихся, разбивает какой-то отрезок на два. Перед тем как разбивать отрезок, выберем на этом отрезке суффикс, который начинается раньше всего, и суффикс, который начинается позже всего. Обновим ответ подстрокой, начинающейся там, где начинается первый суффикс, и заканчивающейся там, где начинается второй суффикс, плюс длина их lcp. После этого разобьем отрезок на два.

Итоговая асимптотика .