Подразделы

Другие разделы

Дата и время

20/12/2024 14:14:27

Авторизация

Динамическое программирование

And Then There Was One Broken Sword: потерянный файл Decoding Morse Sequences SMS Бросание кубика Витрина Возрастающая подпоследовательность Гангстеры Головоломка умножения Зоопарк Копилка Кубический метр Маршрут Палиндром Разложение на простые слагаемые Скобки (3) Скобки (4) Сообщение Строки Фибоначчи

Палиндром

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (2)

Слиянием двух строк называется строка, состоящая из всех букв исходных строк, взятых в порядке следования этих букв в сливаемых строках. Например, для двух строк «xx» и «yy» возможными слияниями являются «xxyy», «xyxy», «xyyx», «yxxy», «yxyx» и «yyxx». Палиндромом называется строка, читаемая одинаково слева направо и справа налево.

Напишите программу, вычисляющую максимальную длину палиндрома, являющегося подстрокой какого-нибудь слияния двух заданных строк. В рассмотренном выше случае в слияниях можно найти следующие палиндромы «x», «y», «xx», «yy», «xyx», «yxy», «xyyx» и «yxxy». Самыми длинными палиндромами являются «xyyx» и «yxxy», имеющие длину 4.

Ввод

В первой строке содержится первая строка, во второй строке вторая строка. Обе строки имеют длину от 1 до 20 букв включительно и содержат только строчные латинские буквы.

Ввод

Вывести одно целое число – максимальную длину палиндрома, являющегося подстрокой слияния двух заданных строк.

Пример ввода

aab
zz

Пример вывода