Задача о наибольшей подпоследовательности-палиндроме
Задача о наибольшей подпоследовательности-палиндрома — это задача поиска длины наибольшей подпоследовательности-палиндрома, которую можно получить вычеркиванием некоторых букв из данной последовательности.
Определения
| Определение: |
| Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. |
| Определение: |
| Подпоследовательностью-палиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. Например, HELOLEH является подпоследовательностью-палиндромом строки HTEOLFEOLEH. |
Решение
Обозначим данную последовательность через , а ее элементы — через . Будем рассматривать возможные подпоследовательности данной последовательности с го по ый символ, обозначим их как . Длины максимальных палиндромов для подпоследовательностей будем записывать в квадратный массив : — длина максимальной подпоследовательности-палиндрома, который можно получить из подпоследовательности .
Начнем решать задачу с простых подпоследовательностей. Для последовательности из одного элемента (то есть подпоследовательности вида ) ответ очевиден — ничего вычеркивать не надо, такая строка будет искомой подпоследовательностью-палиндромом. Для последовательности из двух элементов возможны два варианта: если элементы равны, то мы имеем подпоследовательность-палиндром, ничего вычеркивать не надо. Если же элементы не равны, то вычеркиваем любой.
Пусть теперь нам дана подпоследовательность . Если первый и последний элементы подпоследовательности не совпадают, то один из них нужно вычеркнуть. Тогда у нас останется подпоследовательность или — то есть мы сведем задачу к подзадаче: . Если же первый и последний элементы равны, то мы можем оставить оба, но необходимо знать решение задачи .
Пример
Рассмотрим решение на примере последовательности ABACCBA. Первым делом заполняем диагональ массива единицами, они будут соответствовать подпоследовательностями из одного элемента. Затем начинаем рассматривать подпоследовательности длины два. Во всех подпоследовательностях, кроме , элементы различны, поэтому в соответствующие ячейки запишем , а в — .
Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали, ведущей из левого верхнего угла в правый нижний. Для подпоследовательностей длины получаются следующие значения: в подпоследовательности ABA первый и последний элемент равны, поэтому . В остальных подпоследовательностях первый и последний элементы различны.
BAC:
ACC:
CCB:
CBA:
Продолжая далее аналогичные рассуждения, заполним все ячейки под диагональю и в ячейке получим ответ .
Если же в задаче необходимо вывести не длину, а саму подпоследовательность-палиндром, то дополнительно к массиву длин мы должны построить массив переходов — для каждой ячейки запомнить, какой из случаев был реализован.
