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 Mat[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 Mat[i, j]
== См. также ==
