299
правок
Изменения
1
{{В разработке}}
Задача о '''наибольшей подпоследовательности-палиндрома''' — это задача поиска длины наибольшей подпоследовательности-палиндрома, которую можно получить вычеркиванием некоторых букв из данной последовательности.
== Определения ==
{{Определение|definition='''Палиндромом''' называется строка, которая одинаково читается как слева направо, так и справа налево.}}
'''''Например''''', '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''.
== Решение (алгоритм Манакера) ==[[Файл:Palindrome11.png|200px|thumb|right|Массив длин подпоследовательностей-палиндромов]][[Файл:Palindrome12.png|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>S(i, j - 1)</tex> или <tex>S(i + 1, j)</tex> — то есть мы сведем задачу к подзадаче: вычислять массив <tex>L[i][j] = max(L[i]d_1[j - 1], L[i + 1][j])</tex>. Если же первый и последний элементы равны, то мы можем оставить оба, но необходимо знать ; решение задачи <tex>Sдля палиндромов чётной длины (i + 1, j - 1): L[i][j] = L[i + 1][j - 1] + 2</tex>т. == Пример ==Рассмотрим решение на примере последовательности '''''ABACCBA'''''е. Первым делом заполняем диагональ нахождение массива единицами, они будут соответствовать подпоследовательностями <tex>S(i, i)</tex> из одного элемента. Затем начинаем рассматривать подпоследовательности длины два. Во всех подпоследовательностях, кроме <tex>S(4, 5)</tex>, элементы различны, поэтому в соответствующие ячейки запишем <tex>1</tex>, а в <tex>Ld_2[4][5]</tex> — <tex>2</tex>. Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали, ведущей из левого верхнего угла в правый нижний) получится небольшой модификацией этого. Для подпоследовательностей длины <tex>3</tex> получаются следующие значения: в подпоследовательности '''''ABA''''' первый и последний элемент равны, поэтому <tex>L[1][3] = L[2][2] + 2</tex>. В остальных подпоследовательностях первый и последний элементы различны. '''''BAC''''': <tex>L[2][4] = max(L[2][3], L[3][4]) = 1</tex>
Для быстрого вычисления будем поддерживать '''границы''ACC''''': <tex>L[3][5] = max(L[3][4]l, L[4][5]r) </tex> самого правого из обнаруженных палиндромов (т.е. палиндрома с наибольшим значением <tex>r</tex>). Изначально можно считать <tex>l=0, r= 2-1</tex>.
== См. также ==
