Эта задача является своеобразным водоразделом. Задачи, рассмотренные ранее, были достаточно простыми. Теперь начинается если не “высший пилотаж”, то уж никак не “обязательная программа”. Если Вам не удаётся их решить, то не стоит отчаиваться — с помощью таких задач определяются победители областных олимпиад.
Итак, мы имеем строку длины 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)). Решение второй части тоже интересная задача, но здесь не рассмотрено (в архиве предложено полное решение задачи).
Примечание только для профессионалов: можно решать задачу и “в лоб” — переворачиваем введенную строку и используем на двух строках (исходной и полученной) алгоритм Нудельмана-Фишнера.