Задача о наибольшей общей подпоследовательности-палиндроме

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

Определение:

Палиндромом (англ. palindrom) называется строка, которая одинаково читается как слева направо, так и справа налево.

Наибольшая общая подпоследовательность-палиндром (англ. The longest common palindromic sub-sequence (LCPS)) - задача, являющаяся интересным вариантом классической задачи о поиске наибольшей общей подпоследовательности, которая находит наибольшую общую подпоследовательность среди двух строк так, что она также является палиндромом.