68
правок
Изменения
Нет описания правки
== Определения ==
{{Определение|definition='''Палиндромом (англ. "<i>Palindrome</i>")''' называется строка, которая одинаково читается как слева направо, так и справа налево.}}
{{Определение|definition='''Подпоследовательностью-палиндромом данной строки (англ. "<i>Largest Palindromic Subsequence</i>")''' называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. }}
Например, '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''.
{{Задача
|definition =
Задача о '''наибольшей подпоследовательности {{---}} палиндроме (Largest Palindromic Subsequence)''' {{---}} это задача поиска длины наибольшей подпоследовательности {{---}} палиндроме которую можно получить вычеркиванием некоторых букв из данной последовательности.
}}
== Решение ==
Обозначим данную последовательность через <tex>S</tex>, а ее элементы {{---}} через <tex>S[i], 0 \leqslant i \leqslant n - 1</tex>, где <tex>n</tex> {{---}} длина строки <tex>S</tex>. Будем рассматривать возможные подпоследовательности данной последовательности с <tex>i - </tex>го по <tex>j - </tex>ый символ включительно, обозначив её как <tex>S(i, j)</tex>. Длины максимальных подпалиндромов для данной последовательности будем записывать в квадратный двумерный массив <tex>L</tex>: <tex>L[i][j]</tex> {{---}} длина максимальной подпоследовательности {{---}} палиндрома, который можно получить из последовательности <tex>S(i, j)</tex>.
Начнем решать задачу с простых подпоследовательностей. Для последовательности из одного элемента (то есть подпоследовательности вида <tex>S(i, i)</tex>) ответ очевиден {{---}} ничего вычеркивать не надо, такая строка будет искомой подпоследовательностью-палиндромом. Для последовательности из двух элементов <tex>S(i, i + 1)</tex> возможны два варианта: если элементы равны, то мы имеем подпоследовательность-палиндром, ничего вычеркивать не надо. Если же элементы не равны, то вычеркиваем любой.
== Псевдокод ==
Перед вызовом процедуры заполняем <tex>L[][]</tex> начальными значениями: <tex>L[i][j] = 1</tex> если <tex>i=j</tex>, <tex>L[i][j] = 0</tex>, если <tex>i>j</tex>, в остальных случаях <tex>L[i][j]=-1</tex>.
При первом вызове функции в качестве аргументов передаем индексы первого и последнего элементов исходной строки. Например для строки длиной <tex> N </tex> вызов функции будет иметь следующий вид: <tex>palSubSeq(0,N - 1)</tex>. Искомая же длина будет записана в ячейке <tex>L[0][N-1]</tex>.
'''Функция для вычисления длины палиндрома''' (<tex>left, right</tex> - границы исходной последовательности):
right--
</code>
== См. также ==
* [[Задача о наибольшей общей подпоследовательности]]
* [[Задача о наибольшей возрастающей подпоследовательности]]
* [[Задача о наибольшей общей палиндромной подпоследовательности]]
==Источники информации==
* [[wikipedia:ru:Палиндром|Википедия {{---}} Палиндром]]
* [[wikipedia:Palindrome|Wikipedia {{---}} Palindrome]]
* [http://wcipeg.com/wiki/Longest_palindromic_subsequence Wikipedia {{---}} Longest palindromic subsequence]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
