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''). Общая подпалиндромная последовательность, имеющая максимальную длину, называется '''наибольшей общей подпалиндромной подпоследовательностью''' (англ. ''The longest Longest common palindromic subsequence (LCPS)'') и мы обозначим её как <tex>LCPS(X,Y)</tex>.
}}{{Задача
|definition = '''Наибольшая общая подпалиндромная подпоследовательность''' {{---}} задача, являющаяся интересным вариантом классической задачи о поиске наибольшей общей подпоследовательности, которая также накладывает условия, что эта подпоследовательность должна быть палиндромом.
