1632
правки
Изменения
м
== Определения ==
{{Определение|definition='''Палиндромом (<i>Palindrome</i>)''' называется строка, которая одинаково читается как слева направо, так и справа налево.}}
{{Определение|definition='''Подпоследовательностью {{---}} палиндромом данной строки (<i>Largest Palindromic Subsequence</i>)''' называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. }}
'''''Например''''', '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''.
==Источники информации==
* [[wikipedia:Palindrome|Wikipedia {{---}} Palindrome]]
* [[wikipedia:ru:Палиндром|Википедия {{---}} Палиндром]]
rollbackEdits.php mass rollback
{{Определение|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[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>\mathtt{left, right}</tex> - границы исходной последовательности):
<code style = "display: inline-block;">
'''palSubSeqint'''palSubSeq(left: '''int''', right: '''int'''):
'''if''' L[left][right] == -1
'''if''' s[left] == s[right]
L[left][right] = '''palSubSeq'''(left + 1, right - 1) + 2
'''else'''
L[left][right] = <tex>max</tex>('''palSubSeq'''(left + 1, right), '''palSubSeq'''(left, right - 1))
'''return''' L[left][right]
</code>
'''Функция Процедура для построения искомого палиндрома''' (:*Границы исходной последовательности: <tex>\mathtt{left, right}</tex> {{*Границы искомой подпоследовательности---}} границы исходной последовательностипалиндрома, где правой границей будет длина найденного палиндрома: <tex>\mathtt{palLeft=0, palRight=L[0][n-1]-1}</tex> {{---}} границы искомой):
<code style = "display: inline-block;">
<font color=green>// palindrome {{---}} массив символов, где в palindrome[i] содержится символ искомой последовательности-палиндрома</font>
palChars(left: '''palCharsint'''(left, right: '''int''', palLeft: '''int''', palRight: '''int'''):
'''while''' left <tex>\leqslant </tex> right
'''if''' left == right '''and''' L[left][right] == 1
right--
</code>
== См. также ==
* [[Задача о наибольшей общей подпоследовательности]]
* [[Задача о наибольшей возрастающей подпоследовательности]]
* [[Задача о наибольшей общей палиндромной подпоследовательности]]
==Источники информации==
* [[wikipedia:ru:Палиндром|Википедия {{---}} Палиндром]]
* [[wikipedia:Palindrome|Wikipedia {{---}} Palindrome]]
* [http://wcipeg.com/wiki/Longest_palindromic_subsequence Wikipedia {{---}} Longest palindromic subsequence]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
