Повторяющиеся подпоследовательности
Вы - охотник за сокровищами, путешествующий по миру. Наконец, Вам попал в руки древний манускрипт, в котором указано место где спрятан клад. С первого взгляда текст манускрипта выглядит как бессмысленная строка символов. На самом же деле место расположения клада скрыто в виде наибольшей повторяющейся подпоследовательности текста.
Давайте уточним, что такое наибольшая повторяющаяся подпоследовательность строки. Разобъем сначала входную строку S на две части F и R. Найдем наибольшую общую подпоследовательность L строк F и R (самую длинную строку L, являющуюся подпоследовательностью F и R). Поскольку существует несколько способов разбить S на две части, то существует несколько возможных последовательностей L. Наибольшей повторяющейся подпоследовательностью является самая длинная из них. Например, наибольшая повторяющаяся подпоследовательность строки "ABCABCABAB" является "ABAB", которая получается в результате разбиения "ABCABCABAB" на "ABCABC" и "ABAB".
Вам следует найти наибольшую повторяющуюся подпоследовательность и найти спрятанное сокровище!
Входные данные
Входные данные состоят из нескольких тестов. Каждый тест состоит из одной строки и содержит до 300 заглавных букв. Гарантируется, что каждая входная строка содержит как минимум одну повторяющуюся подпоследовательность.
Последняя строка содержит "#END" и не обрабатывается.
Выходные данные
Для каждого теста в отдельной строке следует вывести наибольшую повторяющуюся подпоследовательность. Если таких подпоследовательностей существует несколько, то вывести любую из них.