|
Название задачи: Подпалиндром. |
 |
Условие
Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. Например, HELOLEH является подпалиндромом строки HTEOLFEOLEH. Напишите программу, находящую в данной строке подпалиндром максимальной длины.Формат входных данных
Строка длиной не более 100 символов, состоящая из заглавных букв латинского алфавита.
Формат выходных данных
В первой строке вывести длину максимального подпалиндрома, а во второй строке сам максимальный подпалиндром. Если таких подпалиндромов несколько, то вывести любой из них.
Решение
Итак, мы имеем строку длины N. Будем искать палиндромы для подстроки с i-го символа по j-ый включительно, то есть писать функцию F(I, J). Хотелось бы, что она возвращала сам палиндром, но это невозможно из-за нехватки памяти. Ограничимся одной длиной. Массив целых 100 * 100 в памяти помещается свободно. Размещаем граничные случаи: F(I, I) = 1 и F(I, J) = 0, если I > J. Теперь в рассматриваемой подстроке отделяем первый символ. Есть две возможности (какая из них реализуется, пока не знаем). Отделенный символ не участвует в образовании максимального подпалиндрома - тогда F(I, J) = F(I + 1, J). Если же участвует, то ищем в подстроке с конца символ, совпадающий с отделенным (пусть его позиция K), тогда F(I, J) = 2 + F(I + 1, K - 1). Надо предусмотреть еще случай I = K, а затем отсекать рекурсию известным способом. Получается примерно следующее:
Function F(i, j : Integer) : Integer; var Ch : Char; R1, R2 : Integer; k : byte; begin if Mat[i, j] = -1 then BEGIN k := j; while Inp[i] <> Inp[k] do dec(k); R1 := F(i + 1, j); if i <> k then R2 := F(i + 1, k - 1) + 2 else R2 := 1; if R1 > R2 then Mat[i, j] := R1 else Mat[i, j] := R2 END; F := Mat[i, j] end;
Итеративно заполнять массив тоже можно, но при этом "стандартный" двойной цикл от 1 до N не годится. Попробуйте, такое решение тоже существует...
Первая, наиболее сложная, часть задачи решена (достаточно вызвать F(1, N)). Решение второй части тоже интересная задача, но здесь не рассмотрено (в архиве предложено полное решение задачи).
Примечание только для профессионалов: можно решать задачу и "в лоб" - переворачиваем введенную строку и используем на двух строках (исходной и полученной) алгоритм Нудельмана-Фишнера.
