Изменения

'''[[Задача о наибольшей общей подпоследовательности]]''' (англ. ''longest common subsequence (LCS)'') - классическая и хорошо изученная проблема. В данной статье мы рассмотрим её модификацию, где это эта последовательность также должна быть палиндромом.

'''Наибольшая общая подпалиндромная подпоследовательность-палиндром''' (англ. ''The longest common palindromic sub-sequence (LCPS)'') - задача, являющаяся интересным вариантом классической задачи о поиске наибольшей общей подпоследовательности, которая находит наибольшую общую подпоследовательность среди двух строк так, что она также является палиндромом. ==Постановка задачи==Мы предполагаем конечный алфавит <tex>\sum</tex>. Для строки <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 palindromicsubsequence''). Общая подпалиндромная последовательность, имеющая максимальную длину, называется '''наибольшей общей подпалиндромной подпоследовательностью''' (англ. ''The longest common palindromic sub-sequence (LCPS)'') и мы обозначим её как <tex>LCPS(X,Y)</tex>. ==Динамическое программирование==