Пончик Чародея
Ваш хозяин уехал в город на день. Вы могли бы провести этот день в спокойствии, не слыша его упреков. Однако он поручил вам приготовить тесто для пончиков к вечеру. Поскольку он так любит пончики, он не может обойтись без десятка пончиков в день. Какая работа для такого прекрасного дня.
Но на прошлой неделе вы подслушали магическое заклинание, которое использовал ваш хозяин. Пришло время его попробовать. Вы произнесли заклинание на метлу, стоящую в углу кухни. С вспышкой света метла обзавелась двумя руками и двумя ногами и ожила. Вы приказали ей, и она принесла ингредиенты из кладовой и начала месить тесто. Заклинание сработало, и как быстро она его замесила!
Через несколько минут на кухонном столе выросла высокая куча теста. Этого хватило бы на следующую неделю. "Хорошо, остановись теперь," — приказали вы. Но она не остановилась. Помогите! Вы не знали заклинания, чтобы остановить её! Вскоре кухонный стол был заполнен сотнями кусков теста, и она всё ещё работала так быстро, как могла. Если вы не остановите её сейчас, вы задохнётесь на кухне, заполненной тестом.
Подождите, разве ваш хозяин не записывал свои заклинания в свои записные книжки? Вы пошли в его кабинет и нашли записную книжку, в которой было записано заклинание прекращения.
Но это была не вся история. Заклинание, написанное в записной книжке, не так легко читается другими. Он использовал пластиковую модель пончика в качестве записной книжки для записи заклинания. Он разделил поверхность модели в форме пончика на квадратную сетку (Рисунок 1) и заполнил её буквами (Рисунок 2). Он спрятал заклинание так тщательно, что узор на поверхности выглядел бессмысленным. Но вы знали, что он написал узор так, чтобы заклинание "появлялось" более одного раза (см. следующий абзац для точных условий). Заклинание не обязательно было написано слева направо, но в любом из 8 направлений, а именно слева направо, справа налево, сверху вниз, снизу вверх и в 4 диагональных направлениях.
Ваша задача — найти заклинание как самую длинную строку, которая появляется более одного раза. Здесь строка считается появляющейся более одного раза, если существуют квадратные последовательности, содержащие строку на пончике, которые удовлетворяют следующим условиям.
Каждая квадратная последовательность не пересекается сама с собой. (Две квадратные последовательности могут делить некоторые квадраты.)
Квадратные последовательности начинаются с разных квадратов и/или идут в разных направлениях.
Обратите внимание, что палиндром (т.е. строка, которая одинакова, если читать её в обратном порядке) удовлетворяет первому условию и "появляется" дважды. Узор на пончике дан в виде матрицы букв следующим образом.
ABCDEFGHIJKL
Обратите внимание, что поверхность пончика не имеет концов; верхняя и нижняя стороны, а также левая и правая стороны узора соответственно соединены. Могут быть квадратные последовательности длиннее как вертикальной, так и горизонтальной длины узора. Например, из буквы F в приведённом выше узоре строки в самых длинных неперекрывающихся последовательностях в направлении 8 направлений следующие.
FGHEFKDEJCHIBGLAFJBFIDGJAHKBELCFEHGFALGBIHCJEDKFBJFCLEBKHAJGDI
Пожалуйста, напишите программу, которая найдёт магическое заклинание, прежде чем вы задохнётесь от кусков теста для пончиков.
Входные данные
Входные данные представляют собой последовательность наборов данных. Каждый набор данных начинается с строки из двух целых чисел h и w, которые обозначают размер узора, за которыми следуют h строк из w заглавных букв от A до Z включительно, которые обозначают узор на пончике. Вы можете предположить, что 3 ≤ h ≤ 10 и 3 ≤ w ≤ 20.
Конец ввода обозначается строкой, содержащей два нуля.
Выходные данные
Для каждого набора данных выведите магическое заклинание. Если существует более одной самой длинной строки одинаковой длины, первой в словарном порядке должна быть заклинание. Известно, что заклинание состоит как минимум из двух букв. Если заклинание не найдено, выведите 0 (ноль).