299
правок
Изменения
→Псевдокод
Если же в задаче необходимо вывести не длину, а саму подпоследовательность-палиндром, то дополнительно к массиву длин мы должны построить массив переходов — для каждой ячейки запомнить, какой из случаев был реализован.
Размещаем граничные случаи: <tex>F(I, I) =1</tex> и <tex>F(I, J) = Псевдокод 0</tex>, если <tex>I > J</tex>. Теперь в рассматриваемой подстроке отделяем первый символ. Есть две возможности (какая из них реализуется, пока не знаем). Отделенный символ не участвует в образовании максимального подпоследовательности-палиндрома — тогда <tex>F(I, J) =F(I + 1, J)</tex>. Если же участвует, то ищем в подстроке с конца символ, совпадающий с отделенным (пусть его позиция <tex>K</tex>), тогда <tex>F(I, J) =2 + F(I + 1, K – 1)</tex>. Надо предусмотреть еще случай <tex>I = K</tex>, а затем отсекать рекурсию.Получается следующая функция: Function F(i, j) if L[i, j] == -1 k = j while S[i] <> S[k] k-- R1 = F(i + 1, j) if i <> k R2 = F(i + 1, k - 1) + 2 else R2 = 1 if R1 > R2 L[i, j] = R1 else L[i, j] = R2 return L[i, j]
== Литература ==
