LCS问题

前几天被问到了LCS（最长公共子序列）问题，不会，正好学习一下。

LCS是求两个字符串，最长的公共部分，中间可以间隔其他的元素。例如，字符串s1=''mzjawxu'',s2=''xmjyauz'',仔细分析下，大体可以看出最长公共子序列是''mjau'',我们需要一套科学严格的方法来求解。这个问题是DP问题（动态规划问题）。动态规划问题：就是当前问题的求解依赖于上一个子问题，上一个子问题又依赖于前一个子问题，子问题无限递归。

按照算法导论上面的描述，对一个两个字符串X，Y，和它们的最长公共子序列Z，有如下的性质：

1. 如果Zk=Xi=Yj，那么Zk-1是字符串Xi-1，Yj-1的最长公共子序列。

   对一个最长公共子序列，这个序列中的字符串，每个元素在X,Y中肯定有相等的元素，这样才叫公共序列，那么如果Zk-1是字符串Xi-1，Yj-1的最长公共子序列，而且Zk=Xi=Yj，Zk在X，Y中都有公共的元素，那么序列Z肯定是X，Y的最长公共子序列。

2. 如果Xi!=Yj,那么Xi!=Zk,就表明了Z是Xi-1和Yj的最长公共子序列。

   说明一下，这里Yj和Zk的关系不确定，可能Yj和Zk相等，也可能不相等。在Xi=Yj的前提下，假设Xi=Zk，同时Z是Xi-1和Yj的最长公共子序列，这时，Xi=Zk，证明了在Xi-1之外，又找到了公共的子序列。所以Z应该是Xi,Yj的最长子序列，这与假设矛盾。

3. 如果Xi!=Yj,那么Yi!=Zk,就表明了Z是Xi和Yj-1的最长公共子序列。

从上面的3条性质可以看出这两个规律：

1. 如果Xi=Yj,那么这个最长公共子序列就应该是Xi-1,Yj-1的最长子序列然后在加上Xi。很明显在Xi-1，Yj-1之外有找到了相同的公共元素，这个最长公共子序列应该在包括这个公共元素。
2. 如果Xi!=Yj,可以想到X，Y的公共子序列 中，可能包括Xi，也可能包括Yj,但是这两个不可能同时出现，可能包括Xi的，不包括Yj的应该是Xi和Yj-1的公共子序列，包括Yj的不包括Xi的，应该是Xi-1和Yj的公共子序列，因为要求最长公共子序列，所以当Xi!=Yj的时候，最长公共子序列应该取，Xi和Yj-1，Xi-1和Yj的公共子序列的最大值。

递推公式

                                      

     从上面的公式可以看出，LCS问题，求X，Y的最长公共子序列转化为Xi-1,Yj-1的子问题了，这样就是动态规划问题。可以看出这个问题的复杂度是O（i*j）。这个递归问题可以用二维数组解决。例子：X=''mzjawxu'',Y=''xmjyauz'',求它的最长公共子序列。

                                     

     上面的二维数组，黑色箭头代表找到了一个相同公共元素，这个元素应该在公共子序列中，这个元素和前面元素的最长子序列的并集，组成整个最长的子序列。每个元素的值表示每个字符串之间的最长公共子序列的长度，假设当前元素的位置（Xi,Yj）,如果横坐标和纵坐标的字符相等，那么它的值等于(Xi-1,Yj-1)+1,如果横坐标和纵坐标的字符不相等，那么它的值等于max((Xi-1,Yj),(Xi,Yj-1)),这个二维数组完全映射了上面的那个递推公式。把所有子字符串的匹配的可能全部展示出来，从X，Y的字符串的最开始，递归后面的字符串。最后得到这个二维数组，数字最大的就是最长子序列的长度。

程序：

  1 #include 
  2 
  3 int data[8][8]={0};                 //初始化为全是0
  4 char *s1="mzjawxu";
  5 char *s2="xmjyauz";
  6 void print(int i,int j);
  7 int main(){
  8    int i=1,j=1;
  9    for(i=1;i<8;i++){
 10      for(j=1;j<8;j++){
 11         if(*(s1+i-1)==*(s2+j-1)){     //如果两个元素相同，那么这个元素的值等于对角的元素的值加一
 12            data[i][j]=data[i-1][j-1]+1;
 13         }else{                        //如果两个元素不同，取左侧元素和上方元素的最大值，这个值也就是Xi-1,Yj和Xi,Yj-1公共字串的最大长度
 14            data[i][j]=data[i][j-1]>data[i-1][j]?data[i][j-1]:data[i-1][j];
 15         }
 16 
 17      }
 18    }
 19    print(i,j);
 20 }
 21 
                            //递归打印最大公共子序列
 22 void print(int i,int j){
 23   if(i==0||j==0)
 24       return;
 25   if(*(s1+i-1)==*(s2+j-1)){
 26     print(i-1,j-1);
 27     printf("%c",*(s1+i-1));
 28   }else if(data[i][j-1]>data[i-1][j]){
 29     print(i,j-1);
 30   }else{
 31     print(i-1,j);
 32   }
 33 }

运算结果mjau

     

总结：

       解决LCS问题的关键在于理解那两个情况的递推公式，把问题转化为子问题，递归到最后，子问题最终会是一个很简单的容易解答的问题，那么顺着最开始的子问题往回推倒父问题，一步一步就得到整个问题的答案。

参考：

1.