55
правок
Изменения
Нет описания правки
В этой статье мы рассмотрим задачу, которая объединяет две вышеперечисленные задачи в одну.
{{Определение
|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''). Общая подпалиндромная последовательность, имеющая максимальную длину, называется '''наибольшей общей подпалиндромной подпоследовательностью''' (англ. ''Longest longest common palindromic subsequence (LCPS)'') и мы обозначим её как <tex>LCPS(X,Y)</tex>.
}}{{Задача
|definition = '''Наибольшая общая подпалиндромная подпоследовательность''' {{---}} задача, являющаяся интересным вариантом классической задачи о поиске наибольшей общей подпоследовательности, которая также накладывает условия, что эта подпоследовательность должна быть палиндромом.
Заметим, что в качестве подзадач для <tex>LCPS</tex>, в которых мы можем посчитать ответ, логично взять подпоследовательность от <tex>X</tex> и от <tex>Y</tex>. Основываясь на этом наблюдении мы сформулируем следующую теорему, которая доказывает оптимальную подструктуру свойств задачи <tex>LCPS</tex>, что даст возможность воспользоваться идеей [[Динамическое программирование | динамического программирования]].
{{Теорема
|statement=Пусть <tex>X</tex> и <tex>Y</tex> {{--- }} две последовательности длин <tex>n</tex> и <tex>m</tex> соответственно, а <tex>X_{i,j}</tex> и <tex>Y_{ik,jl}</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, u-1}</tex> {{---}} НОПП от подпоследовательностей <tex>X_{i+1,j-1}</tex> и <tex>Y_{k+1,l-1}</tex>.
