Изменения

 '''Наибольшая общая подпалиндромная подпоследовательность''' (англ. ''The longest common palindromic subsequence (LCPS)'') {{---}} задача, являющаяся интересным вариантом классической задачи о поиске наибольшей общей подпоследовательности, которая также накладывает условия, что эта подпоследовательность должна быть палиндромом.{{ЗадачаОпределение|definition = Для последовательности <tex>X</tex>, мы обозначим её подпоследовательность <tex>x_{i}...x_{j}\ (1 \leqslant i \leqslant j \leqslant n)\ </tex> как <tex>X_{i,j}</tex>. Для двух последовательностей <tex>X</tex> и <tex>Y</tex>, если общая подпоследовательность <tex>Z</tex> последовательностей <tex>X</tex> и <tex>Y</tex> является палиндромом, то <tex>Z</tex> называется '''общей подпалиндромной подпоследовательностью''' (англ. ''common palindromic subsequence''). Общая подпалиндромная последовательность, имеющая максимальную длину, называется '''наибольшей общей подпалиндромной подпоследовательностью''' (англ. ''The longest common palindromic subsequence (LCPS)'') и мы обозначим её как <tex>LCPS(X,Y)</tex>.}}{{Задача|definition = '''Наибольшая общая подпалиндромная подпоследовательность''' (англ. ''The longest common palindromic subsequence (LCPS)'') {{---}} задача, являющаяся интересным вариантом классической задачи о поиске наибольшей общей подпоследовательности, которая также накладывает условия, что эта подпоследовательность должна быть палиндромом.

|statement=Пусть <tex>X</tex> и <tex>Y</tex> - две последовательности длин <tex>n</tex> и <tex>m</tex> соответственно, а <tex>X_{i,j}</tex> и <tex>Y_{i,j}</tex> {{---}} две подпоследовательности последовательностей <tex>X</tex> и <tex>Y</tex> соответственно. Пусть <tex>Z = z_{1}z_{2}...z_{u}</tex> {{- --}} наибольшая общая подпалиндромная последовательность двух подпоследовательностей <tex>X_{i,j}</tex> и <tex>Y_{k,l}</tex>. Тогда выполняются следующие утверждения,

# Если <tex>x_i=x_j=y_k=y_l=a</tex> (для произвольного <tex>a</tex>), тогда <tex>z_1=z_u=a</tex> и <tex>z_2...z_Z_{2, u-1}</tex> {{---}} наибольшая общая палиндромная подпоследовательность НОПП от подпоследовательностей <tex>X_{i+1,j-1}</tex> и <tex>Y_{k+1,l-1}</tex>.# Если <tex>x_i=x_j=y_k=y_l</tex> не выполняется, то <tex>Z</tex> {{---}} наибольшая общая палиндромная подпоследовательность НОПП от подпоследовательностей (<tex>X_{i+1,j}</tex> и <tex>Y_{k,l}</tex>) или (<tex>X_{i,j-1}</tex> и <tex>Y_{k,l}</tex>) или (<tex>X_{i,j}</tex> и <tex>Y_{k+1,l}</tex>) или (<tex>X_{i,j}</tex> и <tex>Y_{k,l-1}</tex>).

'''return''' (2 + lcps(ans[i + 1, ][j - 1, ][k + 1, ][l - 1)) ]

'''return''' max(lcps(ans[i + 1, ][j, ][k, ][l), lcps(i, j - 1, k, l), lcps(i, j, k + 1, l), lcps(i, j, k, l - 1))]