Изменения

'''[[Задача о наибольшей общей подпоследовательности]]''' (англ. ''longest common subsequence (LCS)'') {{-- -}} классическая и хорошо изученная проблема. В данной статье мы рассмотрим её модификацию, где эта последовательность также должна быть палиндромом.{{Определение|definition='''Палиндромом''' (англ. ''palindrom'') называется последовательность, которая одинаково читается как слева направо, так и справа налево.}}'''Наибольшая общая подпалиндромная подпоследовательность''' (англ. ''The longest common palindromic sub-sequence (LCPS)'') - задача, являющаяся интересным вариантом классической задачи о поиске наибольшей общей подпоследовательности, которая находит наибольшую общую подпоследовательность среди двух последовательностей так, что она также является палиндромом.

==Постановка задачи==Для последовательности <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 common palindromic subsequence (LCPSLPS)'') и мы обозначим её как <tex>LCPS(X,Y)</tex>- также хорошо изучена.

==Динамическое программирование==Заметим, что естественные классы подзадач для <tex>LCPS</tex> соответствуют парам подпоследовательностей из двух входных последовательностей. Основываясь на этом наблюдении В этой статье мы сформулируем следующую теоремурассмотрим задачу, которая доказывает оптимальную подструктуру свойств объединяет две вышеперечисленные задачи <tex>LCPS</tex>в одну.

'''Наибольшая общая подпалиндромная подпоследовательность''' (англ. ''The longest common palindromic subsequence (LCPS)'') {{---}} задача, являющаяся интересным вариантом классической задачи о поиске наибольшей общей подпоследовательности, которая находит наибольшую общую подпоследовательность среди двух последовательностей так, что она также является палиндромом.{{Задача|definition ===Теорема 1===Пусть Для последовательности <tex>X</tex> и <tex>Y</tex> - две последовательности длин <tex>n</tex> и <tex>m</tex> соответственно, а мы обозначим его подпоследовательность <tex>X_x_{i,}...x_{j}(1 \leqslant i \leqslant j \leqslant n)</tex> и как <tex>Y_X_{i,j}</tex> - две подпоследовательности . Для двух последовательностей <tex>X</tex> и <tex>Y</tex> соответственно. Пусть , если общая подпоследовательность <tex>Z = z_{1}z_{2}...z_{u}</tex> - наибольшая общая подпалиндромная последовательность двух подпоследовательностей последовательностей <tex>X_{i,j}X</tex> и <tex>Y_{k,l}Y</tex>. Тогда выполняются следующие утвержденияявляется палиндромом,#Если то <tex>x_i=x_j=y_k=y_l=aZ</tex> называется '''общей подпалиндромной подпоследовательностью''' (для произвольного <tex>a</tex>англ. ''common palindromic subsequence''). Общая подпалиндромная последовательность, тогда <tex>z_1=z_u=a</tex> и <tex>z_2имеющая максимальную длину, называется '''наибольшей общей подпалиндромной подпоследовательностью''' (англ...z_{u-1}</tex> - наибольшая общая палиндромная подпоследовательность от подпоследовательностей <tex>X_{i+1,j-1}</tex> ''The longest common palindromic subsequence (LCPS)'') и мы обозначим её как <tex>Y_{k+1LCPS(X,l-1}Y)</tex>.#Если <tex>x_i}}==x_jНаивное решение=y_k=y_l</tex> не выполняетсяМожно придумать такое решение данной задачи: найти наибольшую общую подпоследовательность, то <tex>Z</tex> - наибольшая общая палиндромная в ней найти наибольшую подпалиндромную подпоследовательность от подпоследовательностей (<tex>X_{i+1. Но,j}</tex> и <tex>Y_{kк сожалению,l}это решение '''неверно'''.===Контрпример===Возьмем 2 последовательности </tex>) или (<tex>X_{i,j-X=1\ 2\ 3\ 1}</tex> и <tex>Y_{k,l}</tex>) или (<tex>X_{i,j}</tex> и <tex>Y_{k+Y=1,l}</tex>) или (<tex>X_{i,j}</tex> и <tex>Y_{k,l-\ 1}\ 2\ 3</tex>).

Наибольшей общая подпоследовательность данных последовательностей равна <tex>LCS(X,Y) = 1\ 2\ 3</tex> и в ней наибольшая подпалиндромная последовательность имеет длину <tex>1</tex>. Но очевидно, что на самом деле последовательность <tex>Z=1\ 1</tex> является наибольшим общей палиндромной подпоследовательностью <tex>X</tex> и <tex>Y</tex> и имеет длину <tex>2</tex>.==[[Динамическое программирование]]==Заметим, что в качестве подзадач для <tex>LCPS</tex>, в которых мы можем посчитать ответ, логично взять подпоследовательность от <tex>X</tex> и от <tex>Y</tex>. Основываясь на этом наблюдении мы сформулируем следующую теорему, которая доказывает оптимальную подструктуру свойств задачи <tex>LCPS</tex>.{{Теорема|statement=Пусть <tex>X</tex> и <tex>Y</tex> - две последовательности длин <tex>n</tex> и <tex>m</tex> соответственно, а <tex>X_{i,j}</tex> и <tex>Y_{i,j}</tex> {{---}} две подпоследовательности последовательностей <tex>X</tex> и <tex>Y</tex> соответственно. Пусть <tex>Z = z_{1}z_{2}...z_{u}</tex> - наибольшая общая подпалиндромная последовательность двух подпоследовательностей <tex>X_{i,j}</tex> и <tex>Y_{k,l}</tex>. Тогда выполняются следующие утверждения,#Если <tex>x_i=x_j=y_k=y_l=a</tex> (для произвольного <tex>a</tex>), тогда <tex>z_1=z_u=a</tex> и <tex>z_2...z_{u-1}</tex> {{---}} наибольшая общая палиндромная подпоследовательность от подпоследовательностей <tex>X_{i+1,j-1}</tex> и <tex>Y_{k+1,l-1}</tex>.#Если <tex>x_i=x_j=y_k=y_l</tex> не выполняется, то <tex>Z</tex> {{---}} наибольшая общая палиндромная подпоследовательность от подпоследовательностей (<tex>X_{i+1,j}</tex> и <tex>Y_{k,l}</tex>) или (<tex>X_{i,j-1}</tex> и <tex>Y_{k,l}</tex>) или (<tex>X_{i,j}</tex> и <tex>Y_{k+1,l}</tex>) или (<tex>X_{i,j}</tex> и <tex>Y_{k,l-1}</tex>).}}На основании теоремы 1 мы напишем следующую рекурсивную формулу для длины наибольшей общей подпалиндромной подпоследовательности:

2+lcps[i+1,j-1,k+1,l-1]&&;&(i < j)\ and\ (k < l)\ ansand\ (x_i=x_j=y_k=y_l)\\

Где <tex>lcps[i,j,k,l]</tex> {{--- }} длина наибольшей общей палиндромной подпоследовательности от <tex>X_{i,j}</tex> и <tex>Y_{k,l}</tex>. Длина наибольшей общей палиндромной подпоследовательности от последовательностей <tex>X</tex> и <tex>Y</tex> будет расположена в <tex>lcps[1,n,1,m]</tex>. Мы можем вычислить эту длину за время <tex>O(n^4)</tex> используя динамическое программирование. ===Реализация===Будем использовать динамику с запоминанием ответа. Оформим решения в виде рекурсивной функции <tex>lcps</tex>, которая возвращает ответ для подзадачи, на которую она была вызвана.<br> В массиве <tex>ans</tex> хранятся ответы для подзадач. До запуска функции <tex>lcps</tex> заполним массив <tex>ans</tex> <tex>-1</tex> и будем использовать такую логику: мы имеем подзадачу <tex>lcps(i,j,k,l)</tex>, если <tex>ans[i][j][k][l] = -1</tex>, то значение для данной подзадачи мы еще не вычисляли и именно этим мы и займемся, иначе значение уже посчитано и мы можем просто вернуть <tex>ans[i][j][k][l]</tex>. Так как каждое значение считается не более одного раза, мы получим асимптотику <tex>O(n^4)</tex>. ===Псевдокод=== '''int''' lcps (i: '''int''', j: '''int''', k: '''int''', l: '''int''') '''if''' (ans[i][j][k][l] <tex> \neq </tex> -1) <span style="color:Green">// если так, то значение уже посчитано и нужно просто его вернуть</span> '''return''' ans[i][j][k][l] '''if''' (i > j '''or''' k > l) ans[i][j][k][l] = 0 '''return''' 0 '''if''' (X[i] == X[j] == Y[k] == Y[l]) '''if''' (i == j '''and''' k == l) ans[i][j][k][l] = 1 '''return''' 1 '''else''' tmp = (2 + lcps(i + 1, j - 1, k + 1, l - 1)) '''return''' tmp ans[i][j][k][l] = tmp tmp = '''max'''(lcps(i + 1, j, k, l), lcps(i, j - 1, k, l), lcps(i, j, k + 1, l), lcps(i, j, k, l - 1)) ans[i][j][k][l] = tmp '''return''' tmp==См. также==* [[Динамическое программирование]]* [[Задача о наибольшей общей подпоследовательности]]* [[Задача о наибольшей подпоследовательности-палиндроме]]==Источники информации==* [https://www.academia.edu/2015585/Computing_a_Longest_Common_Palindromic_Subsequence Academia.edu {{---}} Computing a Longest Common Palindromic Subsequence]