Изменения

Задача о {{Определение|definition='''наибольшей подпоследовательностиПалиндромом''' (англ. <i>Palindrome</i>) называется строка, которая одинаково читается как слева направо, так и справа налево.}}{{Определение|definition='''Подпоследовательностью-палиндромапалиндромом данной строки''' — это задача поиска длины наибольшей подпоследовательности-палиндрома, которую можно получить вычеркиванием некоторых букв (англ. <i>Largest Palindromic Subsequence</i>) называется последовательность символов из данной последовательностистроки, не обязательно идущих подряд, являющаяся палиндромом. }}Например, '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''.

Обозначим данную последовательность через <tex>S</tex>, а ее элементы — {{---}} через <tex>S[i], 0 \le leqslant i \le 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>S(i, j)</tex>. Если <tex>S[i]</tex> и <tex>S[j]</tex> элементы подпоследовательности не совпадают, то один из них нужно вычеркнуть. Тогда у нас останется подпоследовательность <tex>S(i, j - 1)</tex> или <tex>S(i + 1, j)</tex> {{---}} то есть мы сведем задачу к подзадаче: <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>1 </tex> раз за <tex>O(1)</tex> обращаясь к уже вычисленным элементам. Так как размер массива <tex>n \times n</tex>, то алгоритм работает за <tex>O(n^2)</tex>

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

'''''CBA''''': <tex>L[4][6] = \max(L[4][5], L[5][6]) = 1</tex>

Если же в задаче необходимо вывести не длину, а саму подпоследовательность-палиндром, то дополнительно к массиву длин мы должны построить массив переходов — {{---}} для каждой ячейки запомнить, какой из случаев был реализован.

При первом вызове функции в качестве аргументов передаем индексы первого и последнего элементов исходной строки. Например для строки длиной <tex> N </tex> вызов функции будет иметь следующий вид: <tex>\mathrm{palSubSeq(0,N - 1)}</tex>. Искомая же длина будет записана в ячейке <tex>L[0][N-1]</tex>.

'''Функция для вычисления длины палиндрома''' (:*Границы исходной последовательности: <tex>\mathtt{left, right}</tex> - границы исходной последовательности):

'''palSubSeqint'''palSubSeq(left: '''int''', right: '''int'''):

'''if''' s[left] == s[right] L[left][right] = palSubSeq(left + 1, right - 1) + 2 '''else''' L[left][right] = MAXmax(palSubSeq(left + 1, right), palSubSeq(left, right - 1))

'''Функция Процедура для построения искомого палиндрома''' (:*Границы исходной последовательности: <tex>\mathtt{left, right}</tex> {{*Границы искомой подпоследовательности---}} границы исходной последовательностипалиндрома, где правой границей будет длина найденного палиндрома: <tex>\mathtt{palLeft=0, palRight=L[0][n-1]}</tex> {{---}} границы искомой):

<font color=green>// palindrome {{---}} массив символов, где в palindrome[i] содержится символ искомой последовательности-палиндрома</font> palChars(left: '''palCharsint'''(left, right: '''int''', l1palLeft: '''int''', l2palRight: '''int'''): '''while''' left <tex>\leleqslant </tex> right '''if''' left == right && '''and''' L[left][right] == 1