Изменения

{{В разработке}}Задача о '''наибольшей подпоследовательности-палиндрома''' — это задача поиска длины наибольшей подпоследовательности-палиндрома, которую можно получить вычеркиванием некоторых букв из данной последовательности. 

Для решения этой задачи будет необходимо перебрать все [[Файл:Palindrome11.jpg|200px|thumb|right|Массив длин подпоследовательностей-палиндромов]][[Файл:Palindrome12.jpg|200px|thumb|right|Наглядный массив переходов]]Обозначим данную последовательность через <tex>S</tex>, а ее элементы — через <tex>S[i], 1 \le i \le n</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>OS(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== Пример ==Рассмотрим решение на примере последовательности '''''ABACCBA'''''. Первым делом заполняем диагональ массива единицами, они будут соответствовать подпоследовательностями <tex>S(ni, i)</tex> из одного элемента. Затем начинаем рассматривать подпоследовательности длины два. Во всех подпоследовательностях, d2кроме <tex>S(n4, 5) for i = 0 to n d1[i] = </tex>, элементы различны, поэтому в соответствующие ячейки запишем <tex>1 while i - d1[i] </tex>= 0 && i + d1[i] , а в < n && s[i-d1[i]] == s[i+d1tex>L[i]4] ++d1[i5] d2[i] = 0; while i - d2[i] - 1 </tex> — <tex>= 0 && i + d2[i] 2< n && s[i - d2[i] - 1] == s[i + d2[i]] ++d2[i]/tex>.

=== Алгоритм Манакера ===Сначала поймем как находить все подпоследовательности-палиндромы нечётной длиныПолучается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали, тведущей из левого верхнего угла в правый нижний.е. вычислять массив Для подпоследовательностей длины <tex>d_1[]3</tex>; решение для палиндромов чётной длины (т.е. нахождение массива получаются следующие значения: в подпоследовательности '''''ABA''''' первый и последний элемент равны, поэтому <tex>d_2L[1][3] = L[2][2] + 2</tex>) получится небольшой модификацией этого. В остальных подпоследовательностях первый и последний элементы различны.

Для быстрого вычисления будем поддерживать '''границы''BAC' '''': <tex>L[2][4] = max(lL[2][3], rL[3][4])</tex> самого правого из обнаруженных палиндромов (т.е. палиндрома с наибольшим значением <tex>r</tex>). Изначально можно считать <tex>l=0, r=-1</tex>.

Итак, пусть вычисляем значение '''''ACC''''': <tex>d_1L[3][5] = max(L[3][i4]</tex> для очередного <tex>i</tex>, при этом все предыдущие значения <tex>d_1L[4][5]) = 2</tex> уже подсчитаны.

* Если <tex>i</tex> не находится в пределах текущего палиндрома, т.е. <tex>i>r</tex>, то просто выполним тривиальный алгоритм. Т.е. будем последовательно увеличивать значение '''''CCB''''': <tex>d_1L[i4]</tex>, и проверять каждый раз — правда ли текущая подпоследовательность <tex>[i-d_16] = max(L[i4];i+d_1[i5], L[5]</tex> является палиндромом. Когда найдем первое расхождение, либо когда дойдем до границ строки <tex>S</tex> — останавливаемся: окончательно посчитали значение <tex>d_1[i6]</tex>. После этого мы должны не забыть обновить значения <tex>(l,r)= 2</tex>.

* Рассмотрим случай, когда '''''CBA''''': <tex>i \le r</tex>. Попробуем извлечь часть информации из уже подсчитанных значений <tex>d_1L[5][7]</tex>. А именно, отразим позицию <tex>i</tex> внутри палиндрома <tex>(l,r)</tex>, т.е. получим позицию <tex>j=l+max(r-i)</tex>, и рассмотрим значение <tex>d_1L[5][j6]</tex>. Поскольку <tex>j</tex> — позиция, симметричная позиции <tex>i</tex>, то почти всегда можно просто присвоить <tex>d_1L[i6]=d_1[j7]) = 1</tex>.

Продолжая далее аналогичные рассуждения, заполним все ячейки под диагональю и в ячейке <tex>L[1][Файл:Palindrome1.png|300px|thumb|right|палиндром вокруг фактически "копируется" в палиндром вокруг 7]</tex> получим ответ <tex>i(6)</tex>]].

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

На самом деле, чтобы правильно обрабатывать такие ситуации, надо "обрезать" длину палиндрома, т.е. присвоить <tex>d_1[i]=r-i</tex>. После этого следует пустить тривиальный алгоритм, который будет пытаться увеличить значение <tex>d_1[i]</tex>, пока это возможно.= Псевдокод ==

[[Файл:Palindrome2.png|300px|thumb|right|палиндром с центром в <tex>j</tex> изображен уже "обрезанным" до такой длины, что он впритык помещается во внешний палиндром]] В завершение описания алгоритма сталось только напомнить, что надо не забывать обновлять значения <tex>(l,r)</tex> после вычисления очередного значения <tex>d_1[i]</tex>. Также повторимся, что выше описано рассуждение для вычисления массива нечётных палиндромов <tex>d_1[]</tex>; для массива чётных палиндромов <tex>d_2[]</tex> все рассуждения аналогичны.==== Оценка асимптотики ==Литература ==На первый взгляд не очевидно, что данный алгоритм имеет линейную асимптотику[http: при вычислении ответа для определённой позиции в нем нередко запускается тривиальный алгоритм поиска палиндромов. Однако более внимательный анализ показывает, что алгоритм всё же линеен. (Стоит сослаться на алгоритм построения [[Z-функция|Z-функции]] строки, который внутренне сильно напоминает данный алгоритм, и работает также за линейное время.) В самом деле, легко проследить по алгоритму, что каждая итерация, производимая тривиальным поиском, приводит к увеличению на один границы <tex>r</tex>. При этом уменьшений <tex>r</tex> по ходу алгоритма происходить не можетen. Следовательно, тривиальный алгоритм в сумме совершит лишь <tex>O(n)</tex> действийwikipedia. Учитывая, что, кроме тривиальных поисков, все остальные части алгоритма Манакера очевидно работают за линейное время, мы и получаем итоговую асимптотику: <tex>O(n)<org/tex>. ==== Псевдокод ====Для случая подпоследовательностей нечётной длины, т.е. для вычисления массива <tex>d_1[]<wiki/tex>, получаем такой код:  List d1(n) l = 0, r = -1 for i = 0 to n k = (i > r ? 0 : min(d1[l + r - i], r - i)) + 1 while i + k < n && i - k >= 0 && s[i+k] == s[i-k] ++k d1[iPalindrome Wikipedia — Palindrome] = k-- if i + k > r l = i - k, r = i + k

Для подпоследовательностей чётной длины, т[http://ru.еwikipedia. для вычисления массива <tex>d_2[]<org/wiki/tex>, лишь немного меняются арифметические выражения:  List d2(n) l = 0, r = -1 for i = 0 to n k = (i > r ? 0 : min(d2[l + r - i + 1], r - i + 1)) + 1 while (i + k - 1 < n && i - k >= 0 && s[i + k - 1] == s[i - k]) ++k d2[i%D0%9F%D0%B0%D0%BB%D0%B8%D0%BD%D0%B4%D1%80%D0%BE%D0%BC Википедия — Палиндром] = --k if i + k - 1 > r l = i - k, r = i + k - 1

*[[http://neerc.ifmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B5%D0%B9_%D0%BE%D0%B1%D1%89%D0%B5%D0%B9_%D0%BF%D0%BE%D0%B4%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8 Задача о наибольшей общей подпоследовательности]]*[[Задача о наибольшей возрастающей подпоследовательности]]

== Литература ==*[[wikipedia:Palindrome|Wikipedia — Palindrome]]*[[wikipedia:ru:Палиндром|Википедия — Палиндром]]*[http://e-maxxneerc.ifmo.ru/algowiki/palindromes_count E-Maxx - Нахождение всех подпалиндромовindex.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B5%D0%B9_%D0%B2%D0%BE%D0%B7%D1%80%D0%B0%D1%81%D1%82%D0%B0%D1%8E%D1%89%D0%B5%D0%B9_%D0%BF%D0%BE%D0%B4%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8 Задача о наибольшей возрастающей подпоследовательности]