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

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

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

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

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

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

Для последовательности [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 palindromic subsequence). Общая подпалиндромная последовательность, имеющая максимальную длину, называется наибольшей общей подпалиндромной подпоследовательностью (англ. The longest common palindromic subsequence (LCPS)) и мы обозначим её как [math]LCPS(X,Y)[/math].

Динамическое программирование

Заметим, что естественные классы подзадач для [math]LCPS[/math] соответствуют парам подпоследовательностей из двух входных последовательностей. Основываясь на этом наблюдении мы сформулируем следующую теорему, которая доказывает оптимальную подструктуру свойств задачи [math]LCPS[/math].

Теорема 1

Пусть [math]X[/math] и [math]Y[/math] - две последовательности длин [math]n[/math] и [math]m[/math] соответственно, а [math]X_{i,j}[/math] и [math]Y_{i,j}[/math] - две подпоследовательности последовательностей [math]X[/math] и [math]Y[/math] соответственно. Пусть [math]Z = z_{1}z_{2}...z_{u}[/math] - наибольшая общая подпалиндромная последовательность двух подпоследовательностей [math]X_{i,j}[/math] и [math]Y_{k,l}[/math]. Тогда выполняются следующие утверждения,

1. Если [math]x_i=x_j=y_k=y_l=a[/math] (для произвольного [math]a[/math]), тогда [math]z_1=z_u=a[/math] и [math]z_2...z_{u-1}[/math] - наибольшая общая палиндромная подпоследовательность от подпоследовательностей [math]X_{i+1,j-1}[/math] и [math]Y_{k+1,l-1}[/math].
2. Если [math]x_i=x_j=y_k=y_l[/math] не выполняется, то [math]Z[/math] - наибольшая общая палиндромная подпоследовательность от подпоследовательностей ([math]X_{i+1,j}[/math] и [math]Y_{k,l}[/math]) или ([math]X_{i,j-1}[/math] и [math]Y_{k,l}[/math]) или ([math]X_{i,j}[/math] и [math]Y_{k+1,l}[/math]) или ([math]X_{i,j}[/math] и [math]Y_{k,l-1}[/math]).

На основании теоремы 1 мы напишем следующую рекурсивную формулу для длины наибольшей общей подпалиндромной подпоследовательности:

[math] lcps[i,j,k,l] = \left\{\begin{array}{llcl} 0&&;&i \gt j\ or\ k \gt l\\ 1&&;&(i = j)\ and\ (k = l)\ and\ (x_i=x_j=y_k=y_l)\\ 2+lcps[i+1,j-1,k+1,l-1]&&;&(i \lt j)\ and\ (k \lt l)\ ans\ (x_i=x_j=y_k=y_l)\\ \max{(}lcps[i+1,j,k,l],lcps[i,j-1,k,l],&&;&(i \leqslant j)\ and\ (k \leqslant l)\ and\ not(x_i=x_j=y_k=y_l)\\ lcps[i,j,k+1,l],lcps[i,j,k,l-1]) \end{array}\right. [/math]

Где [math]lcps[i,j,k,l][/math] - длина наибольшей общей палиндромной подпоследовательности от [math]X_{i,j}[/math] и [math]Y_{k,l}[/math]. Длина наибольшей общей палиндромной подпоследовательности от последовательностей [math]X[/math] и [math]Y[/math] будет расположена в [math]lcps[1,n,1,m][/math]. Мы можем вычислить эту длину за время [math]O(n^4)[/math] используя динамическое программирование.