Изменения

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

{{ОпределениеЗадача|definition=Задача о '''Подпоследовательностьюнаибольшей подпоследовательности-палиндромом данной строкипалиндроме''' называется последовательность символов {{---}} это задача о поиске наибольшей подпоследовательности, которую можно получить вычеркиванием некоторых букв из данной строки, не обязательно идущих подрядпоследовательности таким образом, являющаяся что оставшаяся подпоследовательность будет палиндромом. }}

'''''Например''''', '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''. == Решение (алгоритм Манакера) ==Сначала поймем как находить все Обозначим данную последовательность через <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>d_1[]L</tex>; решение для палиндромов чётной длины (т.е. нахождение массива : <tex>d_2L[i][j]</tex>{{---}} длина максимальной подпоследовательности-палиндрома, который можно получить из последовательности <tex>S(i, j) получится небольшой модификацией этого</tex>.

Начнем решать задачу с простых подпоследовательностей. Для быстрого вычисления будем поддерживать '''границы''' последовательности из одного элемента (то есть подпоследовательности вида <tex>S(li, ri)</tex> самого правого из обнаруженных палиндромов (т.е. палиндрома с наибольшим значением <tex>r</tex>)ответ очевиден {{---}} ничего вычеркивать не надо, такая строка будет искомой подпоследовательностью-палиндромом. Изначально можно считать Для последовательности из двух элементов <tex>l=0S(i, r=-i + 1)</tex>возможны два варианта: если элементы равны, то мы имеем подпоследовательность-палиндром, ничего вычеркивать не надо. Если же элементы не равны, то вычеркиваем любой.

ИтакПусть теперь нам дана подпоследовательность <tex>S(i, пусть вычисляем значение j)</tex>d_1. Если <tex>S[i]</tex> для очередного и <tex>S[j]</tex> элементы подпоследовательности не совпадают, то один из них нужно вычеркнуть. Тогда у нас останется подпоследовательность <tex>S(i, j - 1)</tex>или <tex>S(i + 1, при этом все предыдущие значения j)</tex> {{---}} то есть мы сведем задачу к подзадаче: <tex>d_1L[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</tex> не находится в пределах текущего палиндрома][j] =\begin{cases} 1, т.е. <tex>& i>r</tex>= j\\ 0, то просто выполним тривиальный алгоритм. Т.е. будем последовательно увеличивать значение <tex& i >d_1j\\ L[i+ 1]</tex>[j - 1] + 2, и проверять каждый раз — правда ли текущая подпоследовательность <tex>& s[i-d_1] = s[j] \\ \max(L[i];[j - 1], L[i+d_11][ij]]</tex> является палиндромом. Когда найдем первое расхождение), либо когда дойдем до границ строки <tex>S</tex> — останавливаемся: окончательно посчитали значение <tex>d_1& s[i]\neq s[j]\end{cases}</tex>. После этого мы должны не забыть обновить значения <tex>(l,r)</tex>.

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

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