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