最长公共子序列问题

子序列

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

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

公共子序列

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

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

最长公共子序列

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

最长公共子序列示意图

描述：最长公共子序列问题就是求序列, 和,的一个最长公共子序列

用表示序列A的连续前x项构成的子序列，即, , 我们用表示它们的最长公共子序列长度，那原问题等价于求LCS(m,n)。为了方便我们用表示和的一个最长公共子序列

• 令表示子序列考虑最后一项
  (1)

  • 那么它们的最后一项一定是这个元素，为了方便，我们令, 我们用反证法：假设最后一项不是，则要么为空序列（别忘了这个），要么的最后一项是, 且显然有。无论是哪种情况我们都可以把接到这个后面,从而得到一个更长的公共子序列。矛盾！

  • 如果我们从序列中删掉最后一项得到,从序列中也删掉最后一项得到，(多说一句角标为0时，认为子序列是空序列)，则我们从也删掉最后一项得到的序列是。为什么呢？和上面的道理相同，如果得到的序列不是，则它一定比短（注意是个集合！），那么它后面接上元素t得到的子序列也比接上元素得到的子序列短，这与是最长公共子序列矛盾。

  • 因此最后接上元素

  • 

  (2)

  • 仍然设, 或者是空序列（这时是未定义值不等于任何值）。则和至少有一个成立，因为不能同时等于两个不同的值
    (2.1)
    如果，则有，因为根本没的事嘛。
    
    (2.2)
    如果,类似
    
  • 我们事先并不知道，由定义，我们取最大的一个，因此这种情况下,有

• 目前得到的有：
  
  (1)
  (2)

• 一个空序列和任何序列的最长公共子序列都是空序列
  
  (1)
  (2)
  (3)

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）如果，这对应末尾接上

  • （2.1） 如果且
    这对应
    （2.2） 如果且
    这对应

  • （3） ，这对应

• 当时，其实走哪个分支都一样，虽然长度时一样的，但是可能对应不同的子序列，所以最长公共子序列并不唯一

//用来记录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 );
   }
}

原理和代码总结来源于：

• 动态规划法(三)——最长公共子序列
• 动态规划基础篇之最长公共子序列问题