Изменения

{{В разработке}}Задача о '''наибольшей подпоследовательности-палиндрома''' — это задача поиска длины наибольшей подпоследовательности-палиндрома, которую можно получить вычеркиванием некоторых букв из данной последовательности.== Определения =={{Определение|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> {{---}} длина строки <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>.

[[Файл:Palindrome1=== Асимптотика ===Каждый элемент массива мы вычисляем <tex>1</tex> раз за <tex>O(1)</tex> обращаясь к уже вычисленным элементам.png|300px|thumb|right|палиндром вокруг фактически "копируется" в палиндром вокруг Так как размер массива <tex>n \times n</tex>, то алгоритм работает за <tex>iO(n^2)</tex>]]

Однако здесь есть тонкость== Пример ==Рассмотрим решение на примере последовательности '''''ABACCBA'''''. Первым делом заполняем диагональ массива единицами, которую надо обработать правильно: когда "внутренний палиндром" достигает границы внешнего или вылазит за неёони будут соответствовать подпоследовательностями <tex>S(i, тi)</tex> из одного элемента.еЗатем начинаем рассматривать подпоследовательности длины два. Во всех подпоследовательностях, кроме <tex>j-d_1[j]+1 \le lS(3, 4)</tex> (или, что то же самоеэлементы различны, поэтому в соответствующие ячейки запишем <tex>i+d_1[j]-1 \ge r</tex>). Поскольку за границами внешнего палиндрома никакой симметрии не гарантируется, то просто присвоить а в <tex>d_1L[i3]=d_1[j4]</tex> будет уже некорректно: у нас недостаточно сведений, чтобы утверждать, что в позиции {{---}} <tex>i2</tex> палиндром имеет такую же длину.

На самом делеПолучается, чтобы правильно обрабатывать такие ситуациичто мы будем заполнять массив по диагоналям, надо "обрезать" длину палиндрома, т.еначиная с главной диагонали. присвоить Для подпоследовательностей длины <tex>d_1[i]=r-i3</tex>. После этого следует пустить тривиальный алгоритмполучаются следующие значения: в подпоследовательности '''''ABA''''' первый и последний элемент равны, который будет пытаться увеличить значение поэтому <tex>d_1L[0][i2]= L[1][1] + 2</tex>, пока это возможно. В остальных подпоследовательностях первый и последний элементы различны.

[[Файл'''''BAC''''':Palindrome2.png|300px|thumb|right|палиндром с центром в <tex>jL[1][3] = \max(L[1][2], L[2][3]) = 1</tex> изображен уже "обрезанным" до такой длины, что он впритык помещается во внешний палиндром]]

В завершение описания алгоритма сталось только напомнить, что надо не забывать обновлять значения '''''ACC''''': <tex>L[2][4] = \max(lL[2][3],r)</tex> после вычисления очередного значения <tex>d_1L[3][i4]) = 2</tex>.

Также повторимся, что выше описано рассуждение для вычисления массива нечётных палиндромов '''''CCB''''': <tex>d_1L[3][5] = \max(L[3][4], L[4]</tex>; для массива чётных палиндромов <tex>d_2[5]) = 2</tex> все рассуждения аналогичны.==== Оценка асимптотики ====На первый взгляд не очевидно, что данный алгоритм имеет линейную асимптотику: при вычислении ответа для определённой позиции в нем нередко запускается тривиальный алгоритм поиска палиндромов.

Однако более внимательный анализ показывает, что алгоритм всё же линеен. '''''CBA''''': <tex>L[4][6] = \max(Стоит сослаться на известный алгоритм построения L[4][5], L[Z-функции строки5][6], который внутренне сильно напоминает данный алгоритм, и работает также за линейное время.)= 1</tex>

В самом делеПродолжая далее аналогичные рассуждения, легко проследить по алгоритму, что каждая итерация, производимая тривиальным поиском, приводит к увеличению на один границы заполним все ячейки над диагональю и в ячейке <tex>rL[0][6]</tex>. При этом уменьшений <tex>r</tex> по ходу алгоритма происходить не может. Следовательно, тривиальный алгоритм в сумме совершит лишь получим ответ {{---}} <tex>O(n)6</tex> действий.

УчитываяЕсли же в задаче необходимо вывести не длину, чтоа саму подпоследовательность-палиндром, кроме тривиальных поисковто дополнительно к массиву длин мы должны построить массив переходов {{---}} для каждой ячейки запомнить, все остальные части алгоритма Манакера очевидно работают за линейное время, мы и получаем итоговую асимптотику: <tex>O(n)</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;"> '''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>

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

== Литература Источники информации==*[[wikipedia:Palindromeru:Палиндром|Wikipedia — PalindromeВикипедия {{---}} Палиндром]]*[[wikipedia:ru:ПалиндромPalindrome|Википедия — ПалиндромWikipedia {{---}} Palindrome]]*[http://e-maxxwcipeg.rucom/algowiki/palindromes_count ELongest_palindromic_subsequence Wikipedia {{--Maxx - Нахождение всех подпалиндромов}} Longest palindromic subsequence]