68
правок
Изменения
Нет описания правки
== Определения ==
{{Определение|definition='''Палиндромом ''' (англ. "<i>Palindrome</i>")''' называется строка, которая одинаково читается как слева направо, так и справа налево.}}{{Определение|definition='''Подпоследовательностью-палиндромом данной строки ''' (англ. "<i>Largest Palindromic Subsequence</i>")''' называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. }}
Например, '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''.
{{Задача
|definition =
Задача о '''наибольшей подпоследовательности-палиндроме''' {{---}} это задача поиска длины о поиске наибольшей подпоследовательности-палиндроме , которую можно получить вычеркиванием некоторых букв из данной последовательноститаким образом, что оставшаяся подпоследовательность будет палиндромом.
}}
== Решение ==
Обозначим данную последовательность через <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[0][6]</tex> получим ответ {{---}} <tex>6</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> \mathrm{palSubSeq(0, N - 1)}</tex>. Искомая же длина будет записана в ячейке <tex>L[0][N-1]</tex>.
'''Функция для вычисления длины палиндрома''' (: Границы исходной последовательности:*<tex>\mathrm{left, = 0}</tex>*<tex> \mathrm{right= N}</tex> - границы исходной последовательности):
<code style = "display: inline-block;">
'''int palSubSeq'''(left:'''int''', right:'''int'''):
'''if''' L[left][right] == -1
'''if''' s[left] == s[right]
'''return''' L[left][right]
</code>
'''Функция Процедура для построения искомого палиндрома''' (: Границы исходной последовательности:*<tex>\mathrm{left, = 0}</tex>*<tex> \mathrm{right= N}</tex> {{Границы искомой подпоследовательности---}} границы исходной последовательности, палиндрома:*<tex>\mathrm{palLeft=0, }</tex>*<tex> \mathrm{palRight=L[0][nN-1]-1}</tex> {{---}} границы искомой подпоследовательности {{---}} палиндрома):
<code style = "display: inline-block;">
<font color=green>// palindrome {{---}} массив символов, где в palindrome[i] содержится символ искомой последовательности-палиндрома</font>
'''palChars'''(left:'''int''', right:'''int''', palLeft:'''int''', palRight:'''int''')
'''while''' left <tex>\leqslant </tex> right
'''if''' left == right '''and''' L[left][right] == 1
