Изменения

Задача о {{Определение|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> {{Определение|definition='''Палиндромом''' называется строка---}} длина строки <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>) ответ очевиден {{Определение|definition='''Подпоследовательностью---}} ничего вычеркивать не надо, такая строка будет искомой подпоследовательностью-палиндромом данной строки''' называется последовательность символов . Для последовательности из данной строкидвух элементов <tex>S(i, i + 1)</tex> возможны два варианта: если элементы равны, то мы имеем подпоследовательность-палиндром, ничего вычеркивать не надо. Если же элементы не равны, то вычеркиваем любой. Пусть теперь нам дана подпоследовательность <tex>S(i, j)</tex>. Если <tex>S[i]</tex> и <tex>S[j]</tex> элементы подпоследовательности не обязательно идущих подрядсовпадают, являющаяся палиндромомто один из них нужно вычеркнуть. НапримерТогда у нас останется подпоследовательность <tex>S(i, j - 1)</tex> или <tex>S(i + 1, '''''HELOLEH''''' является подпоследовательностьюj)</tex> {{---палиндромом строки '''''HTEOLFEOLEH'''''. }}то есть мы сведем задачу к подзадаче: <tex>L[i][j] = \max(L[i][j - 1], L[i + 1][j])</tex>. Если же первый и последний элементы равны, то мы можем оставить оба, но необходимо знать решение задачи <tex>S(i + 1, j - 1):L[i][j] = L[i + 1][j - 1] + 2</tex>. Таким образом получаем следующее рекуррентное соотношение:  <tex>L[i][j] =\begin{cases} 1, & i = Решение =j\\ 0, & i > j\\ L[i + 1][j - 1] + 2, & s[i] =s[j] \\ \max(L[i][j - 1], L[i + 1][j]), & s[i] \neq s[j]\end{cases}</tex>

Начнем решать задачу с простых подпоследовательностей. Для последовательности из одного элемента (то есть подпоследовательности вида === Асимптотика ===Каждый элемент массива мы вычисляем <tex>S(i, i)1</tex>) ответ очевиден — ничего вычеркивать не надо, такая строка будет искомой подпоследовательностью-палиндромом. Для последовательности из двух элементов раз за <tex>SO(i, i + 1)</tex> возможны два варианта: если элементы равны, то мы имеем подпоследовательность-палиндром, ничего вычеркивать не надообращаясь к уже вычисленным элементам. Если же элементы не равныТак как размер массива <tex>n \times n</tex>, то вычеркиваем любой.алгоритм работает за <tex>O(n^2)</tex>

Рассмотрим решение на примере последовательности '''''ABACCBA'''''. Первым делом заполняем диагональ массива единицами, они будут соответствовать подпоследовательностями <tex>S(i, i)</tex> из одного элемента. Затем начинаем рассматривать подпоследовательности длины два. Во всех подпоследовательностях, кроме <tex>S(3, 4, 5)</tex>, элементы различны, поэтому в соответствующие ячейки запишем <tex>1</tex>, а в <tex>L[3][4]</tex> {{---}} <tex>2</tex>. Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали. Для подпоследовательностей длины <tex>3</tex> получаются следующие значения: в подпоследовательности '''''ABA''''' первый и последний элемент равны, поэтому <tex>L[0][52] = L[1][1] + 2</tex>. В остальных подпоследовательностях первый и последний элементы различны.  '''''BAC''''': <tex>L[1][3] = \max(L[1][2], L[2][3]) = 1</tex> '''''ACC''''': <tex>L[2][4] = \max(L[2][3], L[3][4]) = 2</tex> —  '''''CCB''''': <tex>L[3][5] = \max(L[3][4], L[4][5]) = 2</tex>.

Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали, ведущей из левого верхнего угла в правый нижний. Для подпоследовательностей длины <tex>3</tex> получаются следующие значения: в подпоследовательности '''''ABACBA''''' первый и последний элемент равны, поэтому : <tex>L[14][36] = \max(L[24][25] + 2, L[5][6]) = 1</tex>. В остальных подпоследовательностях первый и последний элементы различны.

'''''BAC''''': Продолжая далее аналогичные рассуждения, заполним все ячейки над диагональю и в ячейке <tex>L[20][46] = max(L[2][3], L[3][4]) = 1</tex>получим ответ {{---}} <tex>6</tex>.

'''''ACC''''': <tex>L[3][5] = max(L[3][4]Если же в задаче необходимо вывести не длину, L[4][5]) = 2</tex>а саму подпоследовательность-палиндром, то дополнительно к массиву длин мы должны построить массив переходов {{---}} для каждой ячейки запомнить, какой из случаев был реализован.

'''''CBA'''''[[Файл: <tex>LPalindrome11.png|200px|Заполнение массива длин (1)]][[5Файл:Palindrome12.png|200px|Заполнение массива длин (2)]][7[Файл:Palindrome13.png|200px|Заполнение массива длин (3)]] = max[[Файл:Palindrome14.png|200px|Заполнение массива длин (L[54)]][6], L[6Файл:Palindrome15.png|200px|Массив переходов][7]) = 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[1i][7j]=-1</tex>. При первом вызове функции в качестве аргументов передаем индексы первого и последнего элементов исходной строки. Например для строки длиной <tex> N </tex> получим ответ вызов функции будет иметь следующий вид: <tex>\mathrm{palSubSeq(60, N - 1)}</tex>. Искомая же длина будет записана в ячейке <tex>L[0][N-1]</tex>.

Если же в задаче необходимо вывести не длину'''Функция для вычисления длины палиндрома''':*Границы исходной последовательности: <tex> \mathtt{left, right}</tex><code style = "display: inline-block;"> '''int''' 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] = max(palSubSeq(left + 1, right), palSubSeq(left, right - 1)) '''return''' L[left][right]</code>'''Процедура для построения искомого палиндрома''':*Границы исходной последовательности: <tex> \mathtt{left, а саму подпоследовательностьright}</tex>*Границы искомой подпоследовательности-палиндромпалиндрома, где правой границей будет длина найденного палиндрома: <tex> \mathtt{palLeft, то дополнительно к массиву длин мы должны построить palRight}</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 palindrome[palLeft++] = S[left++] '''else''' '''if''' S[left] == S[right] palindrome[palLeft++] = S[left++] palindrome[palRight--] = S[right--] '''else''' '''if''' L[left + 1][right] <tex> > </tex> L[left][right - 1] left++ '''else''' right--</code>

== Литература См. также ==* [[Задача о наибольшей общей подпоследовательности]]* [[Задача о наибольшей возрастающей подпоследовательности]]* [http://en.wikipedia.org/wiki/Palindrome Wikipedia — Palindrome[Задача о наибольшей общей палиндромной подпоследовательности]]

==Источники информации==* [[wikipedia:ru:Палиндром|Википедия {{---}} Палиндром]]* [[wikipedia:Palindrome|Wikipedia {{---}} Palindrome]]* [http://ruwcipeg.wikipedia.orgcom/wiki/%D0%9F%D0%B0%D0%BB%D0%B8%D0%BD%D0%B4%D1%80%D0%BE%D0%BC Википедия — ПалиндромLongest_palindromic_subsequence Wikipedia {{---}} Longest palindromic subsequence]