299
правок
Изменения
Нет описания правки
'''''Например''''', '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''.
== Решение ==
Обозначим данную последовательность через <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>.
Если же в задаче необходимо вывести не длину, а саму подпоследовательность-палиндром, то дополнительно к массиву длин мы должны построить массив переходов — для каждой ячейки запомнить, какой из случаев был реализован.
[[Файл: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>.
