Изменения

Задача о '''наибольшей подпоследовательности-палиндрома''' — это задача поиска наибольшей подпоследовательности-палиндрома, которую можно получить вычеркиванием некоторых букв из данной последовательности.== Определения =={{Определение|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>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>OS[i]</tex> и <tex>S[j]</tex> элементы подпоследовательности не совпадают, то один из них нужно вычеркнуть. Тогда у нас останется подпоследовательность <tex>S(n^2i, 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>. Таким образом получаем следующее рекуррентное соотношение:

List d1(n), d2(n)<tex> for L[i = 0 to n d1][ij] = \begin{cases} 1 while , & i - d1[i] >= j\\ 0 , && i > j\\ L[i + d11][ij - 1] < n &+ 2, & s[i-d1[i]] == s[i+d1[i]] ++d1[ij]\\ d2 \max(L[i] = 0; while i - d2[i] j - 1 >= 0 && ], L[i + d21][ij] < n &), & s[i - d2[i] - 1] == \neq s[i + d2[i]j] ++d2[i]\end{cases}</tex>

Для быстрого вычисления будем поддерживать '''границы''' === Асимптотика ===Каждый элемент массива мы вычисляем <tex>1</tex> раз за <tex>O(l, r1)</tex> самого правого из обнаруженных палиндромов (тобращаясь к уже вычисленным элементам.е. палиндрома с наибольшим значением Так как размер массива <tex>rn \times n</tex>). Изначально можно считать , то алгоритм работает за <tex>l=0, r=-1O(n^2)</tex>.

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

* Если <tex>i</tex> не находится в пределах текущего палиндромаПолучается, что мы будем заполнять массив по диагоналям, т.еначиная с главной диагонали. Для подпоследовательностей длины <tex>i>r3</tex>получаются следующие значения: в подпоследовательности '''''ABA''''' первый и последний элемент равны, то просто выполним тривиальный алгоритм. Т.е. будем последовательно увеличивать значение поэтому <tex>d_1L[i0]</tex>, и проверять каждый раз — правда ли текущая подпоследовательность <tex>[i-d_1[i2];i+d_1= L[i]1]</tex> является палиндромом. Когда найдем первое расхождение, либо когда дойдем до границ строки <tex>S</tex> — останавливаемся: окончательно посчитали значение <tex>d_1[i1]+ 2</tex>. После этого мы должны не забыть обновить значения <tex>(l,r)</tex>В остальных подпоследовательностях первый и последний элементы различны.

[[Файл'''''BAC''''':Palindrome1.png|300px|thumb|right|палиндром вокруг фактически "копируется" в палиндром вокруг <tex>iL[1][3] = \max(L[1][2], L[2][3]) = 1</tex>]]

Однако здесь есть тонкость, которую надо обработать правильно'''''ACC''''': когда "внутренний палиндром" достигает границы внешнего или вылазит за неё, т.е. <tex>j-d_1L[j2]+1 [4] = \le l</tex> max(или, что то же самое, <tex>i+d_1L[2][j3]-1 \ge r</tex>). Поскольку за границами внешнего палиндрома никакой симметрии не гарантируется, то просто присвоить <tex>d_1L[i3]=d_1[j4]) = 2</tex> будет уже некорректно: у нас недостаточно сведений, чтобы утверждать, что в позиции <tex>i</tex> палиндром имеет такую же длину.

На самом деле, чтобы правильно обрабатывать такие ситуации, надо "обрезать" длину палиндрома, т.е. присвоить '''''CCB''''': <tex>d_1L[3][i5]=r-i</tex>. После этого следует пустить тривиальный алгоритм\max(L[3][4], который будет пытаться увеличить значение <tex>d_1L[4][i5]) = 2</tex>, пока это возможно.

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

Продолжая далее аналогичные рассуждения, заполним все ячейки над диагональю и в ячейке <tex>L[0][Файл:Palindrome2.png|300px|thumb|right|палиндром с центром в 6]</tex> получим ответ {{---}} <tex>j6</tex> изображен уже "обрезанным" до такой длины, что он впритык помещается во внешний палиндром]].

В завершение описания алгоритма сталось только напомнитьЕсли же в задаче необходимо вывести не длину, что надо не забывать обновлять значения <tex>(lа саму подпоследовательность-палиндром, то дополнительно к массиву длин мы должны построить массив переходов {{---}} для каждой ячейки запомнить,r)</tex> после вычисления очередного значения <tex>d_1[i]</tex>какой из случаев был реализован.

Также повторимся, что выше описано рассуждение для вычисления Последовательность заполнения массива нечётных палиндромов <tex>d_1[]</tex>; для массива чётных палиндромов <tex>d_2[]</tex> все рассуждения аналогичныи массив переходов см.==== Оценка асимптотики ====На первый взгляд не очевидно, что данный алгоритм имеет линейную асимптотику: при вычислении ответа для определённой позиции в нем нередко запускается тривиальный алгоритм поиска палиндромовна изображениях ниже.

Однако более внимательный анализ показывает, что алгоритм всё же линеен[[Файл:Palindrome11. png|200px|Заполнение массива длин (Стоит сослаться на 1)]][[алгоритм построения Z-функции строкиФайл: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>rL[i][j]=-1</tex>. При этом уменьшений первом вызове функции в качестве аргументов передаем индексы первого и последнего элементов исходной строки. Например для строки длиной <tex>rN </tex> вызов функции будет иметь следующий вид: <tex> \mathrm{palSubSeq(0, N - 1)}</tex> по ходу алгоритма происходить не может. Следовательно, тривиальный алгоритм Искомая же длина будет записана в сумме совершит лишь ячейке <tex>O(n)L[0][N-1]</tex> действий.

Учитывая, что, кроме тривиальных поисков, все остальные части алгоритма Манакера очевидно работают за линейное время, мы и получаем итоговую асимптотику'''Функция для вычисления длины палиндрома''':*Границы исходной последовательности: <tex>O(n)\mathtt{left, right}</tex>. <code style ==== Псевдокод ====Для случая подпоследовательностей нечётной длины, т.е. для вычисления массива <tex"display: inline-block;">d_1[]</tex>, получаем такой код:  List d1'''int''' palSubSeq(nleft: '''int''', right: '''int'''): l '''if''' L[left][right] = 0, r = -1 for i '''if''' s[left] == 0 to ns[right] k L[left][right] = palSubSeq(i > r ? 0 : min(d1[l left + r - i]1, r right - i)1) + 12 '''else''' while i + k < n && i - k >= 0 && s L[i+kleft] == s[i-kright] = max(palSubSeq(left ++k1, right), palSubSeq(left, right - 1)) d1'''return''' L[ileft][right] = k-- if i + k </code> r l = i - k'''Процедура для построения искомого палиндрома''':*Границы исходной последовательности: <tex> \mathtt{left, r = i + kright}</tex> Для подпоследовательностей чётной длины*Границы искомой подпоследовательности-палиндрома, т.е. для вычисления массива где правой границей будет длина найденного палиндрома: <tex>d_2[]\mathtt{palLeft, palRight}</tex>, лишь немного меняются арифметические выражения<code style = "display:inline-block;"> List d2(n) l <font color= 0green>// palindrome {{---}} массив символов, r = где в palindrome[i] содержится символ искомой последовательности-1палиндрома</font> for i = 0 to n k = palChars(i > r ? 0 left: '''int''', right: '''int''', palLeft: min(d2[l + r - i + 1]'''int''', r - i + 1palRight: '''int''')) + 1: '''while (i + k - 1 ''' left <tex>\leqslant < n && i - k /tex>right '''if''' left = 0 && s= right '''and''' L[left][right] == 1 palindrome[palLeft++] = S[i left++ k - 1] '''else''' '''if''' S[left] == sS[i - kright]) palindrome[palLeft++] = S[left++k] d2 palindrome[ipalRight--] = S[right--k] '''else''' '''if i ''' L[left + k 1][right] <tex> > </tex> L[left][right - 1 > r] left++ '''else''' l = i right- k, r = i + k - 1</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]