Изменения

{{В разработкеОпределение|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>) ответ очевиден {{---}}ничего вычеркивать не надо, такая строка будет искомой подпоследовательностью-палиндромом. Для последовательности из двух элементов <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, j)</tex> {{Определение|definition---}} то есть мы сведем задачу к подзадаче: <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>. }}Таким образом получаем следующее рекуррентное соотношение:

'''''Например''''', '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''. <tex>L[i][j] =\begin{cases} 1, & i = Решение ==j\\ 0, & i > j\\ L[i + 1][Файл:Palindrome11.png|200px|thumb|right|Массив длин подпоследовательностейj -палиндромов1]+ 2, & s[i]= s[[Файл:Palindrome12.png|200px|thumb|right|Наглядный массив переходов]j]\\Обозначим данную последовательность через <tex>S</tex>, а ее элементы — через <tex>S \max(L[i], 1 \le i \le n</tex> Будем рассматривать возможные подпоследовательности данной последовательности с <tex>i - </tex>го по <tex>[j-</tex>ый символ, обозначим их как <tex>S(i1], j)</tex>. Длины максимальных палиндромов для подпоследовательностей будем записывать в квадратный массив <tex>L</tex>: <tex>L[i+ 1][j]</tex> — длина максимальной подпоследовательности-палиндрома), который можно получить из подпоследовательности <tex>S(& s[i, ] \neq s[j)]\end{cases}</tex>.

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

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

Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали, ведущей из левого верхнего угла в правый нижний. Для подпоследовательностей длины <tex>3</tex> получаются следующие значения: в подпоследовательности '''''ABA''''' первый и последний элемент равны, поэтому <tex>L[10][32] = L[21][21] + 2</tex>. В остальных подпоследовательностях первый и последний элементы различны.

'''''ACCBAC''''': <tex>L[31][53] = \max(L[31][42], L[42][53]) = 21</tex>

'''''CCBACC''''': <tex>L[42][64] = \max(L[42][53], L[53][64]) = 2</tex>

'''''CBACCB''''': <tex>L[53][75] = \max(L[53][64], L[64][75]) = 12</tex>

Продолжая далее аналогичные рассуждения, заполним все ячейки под диагональю и в ячейке '''''CBA''''': <tex>L[14][76]</tex> получим ответ <tex>= \max(L[4][5], L[5][6])= 1</tex>.

Продолжая далее аналогичные рассуждения, заполним все ячейки над диагональю и в ячейке <tex>L[0][6]</tex> получим ответ {{---}} <tex>6</tex>. Если же в задаче необходимо вывести не длину, а саму подпоследовательность-палиндром, то дополнительно к массиву длин мы должны построить массив переходов — {{---}} для каждой ячейки запомнить, какой из случаев был реализован. Последовательность заполнения массива и массив переходов см. на изображениях ниже. [[Файл:Palindrome11.png|200px|Заполнение массива длин (1)]][[Файл:Palindrome12.png|200px|Заполнение массива длин (2)]][[Файл:Palindrome13.png|200px|Заполнение массива длин (3)]][[Файл:Palindrome14.png|200px|Заполнение массива длин (4)]][[Файл:Palindrome15.png|200px|Массив переходов]]

Размещаем граничные случаиПеред вызовом процедуры заполняем <tex>L[][]</tex> начальными значениями: <tex>F(I, I) L[i][j] = 1</tex> и если <tex>i=j</tex>F(I, J) <tex>L[i][j] = 0</tex>, если <tex>I i> Jj</tex>. Теперь в рассматриваемой подстроке отделяем первый символ. Есть две возможности (какая из них реализуется, пока не знаем). Отделенный символ не участвует в образовании максимального подпоследовательности-палиндрома — тогда остальных случаях <tex>F(I, J) L[i][j]= F(I + -1, J)</tex>. Если же участвует, то ищем При первом вызове функции в подстроке с конца символ, совпадающий с отделенным (пусть его позиция качестве аргументов передаем индексы первого и последнего элементов исходной строки. Например для строки длиной <tex>KN </tex>), тогда вызов функции будет иметь следующий вид: <tex>F\mathrm{palSubSeq(I0, J) = 2 + F(I + 1, K – N - 1)}</tex>. Надо предусмотреть еще случай Искомая же длина будет записана в ячейке <tex>I = KL[0][N-1]</tex>. '''Функция для вычисления длины палиндрома''':*Границы исходной последовательности: <tex> \mathtt{left, а затем отсекать рекурсию.right}</tex>Получается следующая функция<code style = "display:inline-block;"> Function F'''int''' palSubSeq(ileft: '''int''', jright: '''int'''): '''if ''' L[i, jleft][right] == -1 k '''if''' s[left] = j= s[right] while S L[ileft] <> S[kright] k-- R1 = FpalSubSeq(i left + 1, jright - 1)+ 2 if i <> k'''else''' R2 L[left][right] = Fmax(palSubSeq(i left + 1, k right), palSubSeq(left, right - 1) + 2) '''return''' L[left][right]</code>'''Процедура для построения искомого палиндрома''':*Границы исходной последовательности: <tex> \mathtt{left, right}</tex>*Границы искомой подпоследовательности-палиндрома, где правой границей будет длина найденного палиндрома: <tex> \mathtt{palLeft, palRight}</tex> else<code style = "display: inline-block;"> R2 <font color= 1green>// palindrome {{---}} массив символов, где в palindrome[i] содержится символ искомой последовательности-палиндрома</font> palChars(left: '''int''', right: '''int''', palLeft: '''int''', palRight: '''int'''): '''while''' left <tex>\leqslant </tex> right '''if R1 > R2''' left == right '''and''' L[left][right] == 1 Lpalindrome[i, jpalLeft++] = R1S[left++] '''else''' L'''if''' S[left] == S[right] palindrome[i, jpalLeft++] = R2S[left++] return Mat palindrome[palRight--] = S[right--] '''else''' '''if''' L[left + 1][right] <tex> > </tex> L[left][i, jright - 1] left++ '''else''' right--</code>

*[[Задача о наибольшей общей подпоследовательности]]*[[Задача о наибольшей возрастающей подпоследовательности]]* [[Задача о наибольшей общей палиндромной подпоследовательности]]

== Литература Источники информации==*[[wikipedia:Palindromeru:Палиндром|Wikipedia — PalindromeВикипедия {{---}} Палиндром]]*[[wikipedia:ru:ПалиндромPalindrome|Википедия — ПалиндромWikipedia {{---}} Palindrome]]* [http://wcipeg.com/wiki/Longest_palindromic_subsequence Wikipedia {{---}} Longest palindromic subsequence]