Изменения

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

Однако здесь есть тонкость, которую надо обработать правильно: когда "внутренний палиндром" достигает границы внешнего или вылазит за неё, т.е. === Асимптотика ===Каждый элемент массива мы вычисляем <tex>j-d_1[j]+1 \le l</tex> (или, что то же самое, раз за <tex>i+d_1[j]-O(1 \ge r)</tex>)обращаясь к уже вычисленным элементам. Поскольку за границами внешнего палиндрома никакой симметрии не гарантируется, то просто присвоить Так как размер массива <tex>d_1[i]=d_1[j]n \times n</tex> будет уже некорректно: у нас недостаточно сведений, чтобы утверждать, что в позиции то алгоритм работает за <tex>iO(n^2)</tex> палиндром имеет такую же длину.

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

Иллюстрация этого случая (на ней палиндром Получается, что мы будем заполнять массив по диагоналям, начиная с центром в главной диагонали. Для подпоследовательностей длины <tex>j3</tex> изображен уже "обрезанным" до такой длины, что он впритык помещается во внешний палиндром)получаются следующие значения: в подпоследовательности '''IMG2''ABA''''' первый и последний элемент равны, поэтому <tex>L[0][2] = L[1][1] + 2</tex>. В остальных подпоследовательностях первый и последний элементы различны.

Также повторимся, что выше описано рассуждение для вычисления массива нечётных палиндромов '''''BAC''''': <tex>d_1L[1][3] = \max(L[1][2], L[2]</tex>; для массива чётных палиндромов <tex>d_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>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>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 Нахождение всех подпалиномовLongest_palindromic_subsequence Wikipedia {{---}} Longest palindromic subsequence]