Изменения

Пусть <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 мы напишем следующую рекурсивную формулу для длины наибольшей общей подпалиндромной подпоследовательности: <tex>lcps[i,j,k,l] = \left\{\begin{array}{llcl}0&&;&i > j\ or\ k > 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 < j)\ and\ (k < 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.</tex> Где <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> используя динамическое программирование.