最长公共子序列问题

2019-03-09 本文已影响0人 whupenger

子序列

一个序列A ＝ a1,a2,……an,中任意删除若干项，剩余的序列叫做A的一个子序列。也可以认为是从序列A按原顺序保留任意若干项得到的序列。

对序列 1,3,5,4,2,6,8,7来说，序列3,4,8,7 是它的一个子序列。
对于一个长度为n的序列，它一共有 $2^n$ 个子序列，有 $(2^n – 1)$ 个非空子序列。
请注意：子序列不是子集，它和原始序列的元素顺序是相关的

公共子序列

顾名思义，如果序列C既是序列A的子序列，同时也是序列B的子序列，则称它为序列A和序列B的公共子序列。

空序列是任何两个序列的公共子序列

最长公共子序列

A和B的公共子序列中长度最长的（包含元素最多的）叫做A和B的公共子序列

最长公共子序列示意图

描述：最长公共子序列问题就是求序列 $A= a_1,a_2,……a_x$ , 和 $B = b_1,b_2,……b_m$ ,的一个最长公共子序列

用 $A_x$ 表示序列A的连续前x项构成的子序列，即 $A_x= a_1,a_2,……a_x$ , $B_y= b_1,b_2,……b_y$ , 我们用 $LCS(x, y)$ 表示它们的最长公共子序列长度，那原问题等价于求LCS(m,n)。为了方便我们用 $L(x, y)$ 表示 $A_x$ 和 $B_y$ 的一个最长公共子序列

令 $x$ 表示子序列考虑最后一项
(1) $A_x ＝ B_y$
- 那么它们 $L(A_x, B_y)$ 的最后一项一定是这个元素 $x$ ，为了方便，我们令 $t = A_x = B_y$ , 我们用反证法：假设 $L(x,y)$ 最后一项不是 $t$ ，则要么 $L(x,y)$ 为空序列（别忘了这个），要么 $L(x,y)$ 的最后一项是 $A_a＝B_b ≠ t$ , 且显然有 $a < x, b < y$ 。无论是哪种情况我们都可以把 $t$ 接到这个 $L(x,y)$ 后面,从而得到一个更长的公共子序列。矛盾！
- 如果我们从序列 $A_x$ 中删掉最后一项 $a_x$ 得到 $A_{x-1}$ ,从序列 $B_y$ 中也删掉最后一项 $b_y$ 得到 $B_{y-1}$ ，(多说一句角标为0时，认为子序列是空序列)，则我们从 $L(x,y)$ 也删掉最后一项 $t$ 得到的序列是 $L(x – 1, y - 1)$ 。为什么呢？和上面的道理相同，如果得到的序列不是 $L(x - 1, y - 1)$ ，则它一定比 $L(x - 1, y - 1)$ 短（注意 $L（，）$ 是个集合！），那么它后面接上元素t得到的子序列 $L(x,y)$ 也比 $L(x - 1, y - 1)$ 接上元素 $t$ 得到的子序列短，这与 $L(x, y)$ 是最长公共子序列矛盾。
- 因此 $L(x, y) = L(x - 1, y - 1)$ 最后接上元素 $t$
- $LCS(A_x, B_y) = LCS(x - 1, y - 1) + 1$
(2) $A_x ≠ B_y$
- 仍然设 $t = L(A_x, B_y)$ , 或者 $L(A_x, B_y)$ 是空序列（这时 $t$ 是未定义值不等于任何值）。则 $t ≠ A_x$ 和 $t ≠ B_y$ 至少有一个成立，因为 $t$ 不能同时等于两个不同的值
  (2.1)
  如果 $t ≠ A_x$ ，则有 $L(x, y)= L(x - 1, y)$ ，因为根本没 $A_x$ 的事嘛。
  $LCS(x,y) = LCS(x – 1, y)$
  (2.2)
  如果 $t ≠ B_y$ ,类似 $L(x, y)= L(x , y - 1)$
  $LCS(x,y) = LCS(x, y – 1)$
- 我们事先并不知道 $t$ ，由定义，我们取最大的一个，因此这种情况下,有 $LCS(x,y) = max(LCS(x – 1, y) , LCS(x, y – 1))$
目前得到的有：
$LCS(x,y) =$
(1) $LCS(x - 1,y - 1) + 1 , 如果A_x ＝ B_y$
(2) $max(LCS(x – 1, y) , LCS(x, y – 1)), 如果A_x ≠ B_y$
一个空序列和任何序列的最长公共子序列都是空序列
$LCS(x,y) =$
(1) $LCS(x - 1,y - 1) + 1 如果A_x ＝ B_y$
(2) $max(LCS(x – 1, y) , LCS(x, y – 1)) 如果A_x ≠ B_y$
(3) $0 如果x = 0或者y = 0$

for x = 0 to n do
    for y = 0 to m do
        if (x == 0 || y == 0) then 
            LCS(x, y) = 0
        else if (Ax == By) then
            LCS(x, y) =  LCS(x - 1,y - 1) + 1
        else 
            LCS(x, y) = ) max(LCS(x – 1, y) , LCS(x, y – 1))
        endif
    endfor
endfor

求最大公共子序列

的值来源的三种情况
- （1） $LCS(x – 1, y – 1) + 1$ 如果 $A_x ＝ B_y$ ，这对应 $L(x,y) = L(x- 1, y- 1)$ 末尾接上 $A_x$
- （2.1） $LCS(x – 1, y)$ 如果 $A_x ≠ B_y$ 且 $LCS(x – 1, y) ≥LCS(x, y – 1)$
  这对应 $L(x,y)= L(x – 1, y)$
  （2.2） $LCS(x, y – 1)$ 如果 $A_x ≠ B_y$ 且 $LCS(x – 1, y) <LCS(x, y – 1)$
  这对应 $L(x,y) = L(x, y – 1)$
- （3） $0 如果 x =0或者y = 0$ ，这对应 $L(x,y)=空序列$
当 $LCS(x – 1, y) ＝ LCS(x, y – 1)$ 时，其实走哪个分支都一样，虽然长度时一样的，但是可能对应不同的子序列，所以最长公共子序列并不唯一

//用来记录Xi和Yj的最长公共子序列的长度
private int[][] c;
//用来标识Xi和Yi的最长公共子序列是由哪种情况得来：c[i][j-1]、c[i-1][j]、c[i][j]+1。 
//该数组能还原出最长公共子序列
private int[][] s;
void LCSLength(String a, String b){
   // x和y的最前端分别加上0
   char[] x = ("0"+a).toCharArray();
   char[] y = ("0"+b).toCharArray();

   c = new int[x.length][y.length];
   s = new int[x.length][y.length];

   // 初始化c、s
   for( int i=0; i<x.length; i++ ){
       c[i][0] = 0;
   }
   for( int i=0; i<y.length; i++ ){
       c[0][i] = 0;
   }

   // 从上到下、从左到右填充c、s数组
   for( int i=1; i<x.length; i++ ){
       for( int j=1; j<y.length; j++ ){
           if( x[i]==y[j] ){
               c[i][j] = c[i-1][j-1]+1;
               s[i][j] = 1;
           }
           else if ( c[i-1][j] >= c[i][j-1] ){
               c[i][j] = c[i-1][j];
               s[i][j] = 2;
           }
           else {
               c[i][j] = c[i][j-1];
               s[i][j] = 3;
           }
       }
   }
}

//根据s数组求最大公共子序列
StringBuilder sb = new StringBuilder();

void CLCS( int i, int j ){
   if ( i==0 || j==0 ) return;
   if ( s[i][j]==1 ) {
       CLCS( i-1,j-1 );
       sb.append( x[i] ); // 为了让公共子序列正序输出，因此需要在递归调用之后将x[i]添加至sb
   }
   else if ( s[i][j]==2 ){
       CLCS( i-1,j );
   }
   else {
       CLCS( i,j-1 );
   }
}

原理和代码总结来源于：

最长公共子序列问题

子序列

公共子序列

最长公共子序列

猜你喜欢

热点阅读