3622
правки
Изменения
Нет описания правки
'''''Например''''', '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''.
== Решение ==
Обозначим данную последовательность через <tex>S</tex>, а ее элементы — через <tex>S[i], 1 0 \le i \le n- 1</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][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(3, 4, 5)</tex>, элементы различны, поэтому в соответствующие ячейки запишем <tex>1</tex>, а в <tex>L[3][4]</tex> — <tex>2</tex>.
Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали. Для подпоследовательностей длины <tex>3</tex> получаются следующие значения: в подпоследовательности '''''ABA''''' первый и последний элемент равны, поэтому <tex>L[0][2] = L[1][1] + 2</tex>. В остальных подпоследовательностях первый и последний элементы различны.
'''''CBA''''': <tex>L[4][6] = max(L[4][5], L[5][6]) = 1</tex>
Продолжая далее аналогичные рассуждения, заполним все ячейки над диагональю и в ячейке <tex>L[0][6]</tex> получим ответ {{---}} <tex>(6)</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>.
При первой первом вызове функции, к в качестве аргументов передаем индексы первого и последнего элементов исходной строки. Например для строки длиной 7 <tex> N </tex> вызов функции будет иметь следующий вид: <tex>palSubSeq(0,6N - 1)</tex>. Искомая же длина будет записана в ячейке <tex>L[0][N-1]</tex>, где <tex>N</tex> — длина исходной строки.
'''Функция для вычисления длины палиндрома ''' (<tex>left, right</tex> - границы исходной последовательности):'''
<code style = "display: inline-block;">
'''palSubSeq'''(left, right)
'''return''' L[left][right]
</code>
'''Функция для построения искомого палиндрома ''' (<tex>left, right</tex> {{--- }} границы исходной последовательности, <tex>l1palLeft=10, l2palRight=L[10][n-1]</tex>{{---}} границы искомой):'''
<code style = "display: inline-block;">
// pal palindrome {{---}} массив Charсимволов, где в palpalindrome[i] содержится символ искомой последовательности-палендромапалиндрома
'''palChars'''(left, right, l1, l2)
'''while''' left <tex>\le</tex> right
'''if''' left == right && L[left][right] == 1
'''else'''
'''if''' sS[left] == sS[right] Palpalindrome[l1palLeft++] = sS[left++] Palpalindrome[l2palRight--] = sS[right] left++ right--]
'''else'''
'''if''' L[left + 1][right] <tex> > </tex> L[left][right - 1]
left++
'''else'''
