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

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

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

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

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

Постановка задачи

Мы предполагаем конечный алфавит [math]\sum[/math]. Для строки [math]X[/math], мы обознамич его подстроку [math]x_{i}...x_{j} (1 \leqslant i \leqslant j \leqslant n)[/math] как [math]X_{i,j}[/math]. Для двух строк [math]X[/math] и [math]Y[/math], если общая подпоследовательность [math]Z[/math] строк [math]X[/math] и [math]Y[/math] является палиндромом, то [math]Z[/math] называется общей подпалиндромной подпоследовательностью (англ. common palindromicsubsequence). Общая подпалиндромная последовательность, имеющая максимальную длину, называется наибольшей общей подпалиндромной подпоследовательностью (англ. The longest common palindromic sub-sequence (LCPS)) и мы обозначим её как [math]LCPS(X,Y)[/math].