devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【动态规划】输出两个序列的所有的最长公共子序列（java）_递归算法 输出最长公共子序列

作者：从前慢现在也慢 | 2024-03-06 22:32:49

赞

踩

递归算法 输出最长公共子序列

要解决的问题就是如何找出两个序列的全部公共子序列。

首先我们要知道公共子序列的定义：给定两个序列X与Y，当另一序列Z既是X的子序列又是Y的子序列时称Z序列是X与Y的公共子序列。

而最长公共子序列为所有Z序列中最长的序列。

那么我们要如何输出呢？

由最长子序列问题的最优子结构性质可以知道，要找出X与Y的最长公共子序列要按照递归的方式进行：

首先匹配两个序列开头的元素，当两个序列开头的两个元素相同时，说明这个开头是子序列的一部分，然后记录该元素继续进行匹配两个序列的第二个元素，如果开头的两个元素不同则需要进行一直匹配也就是保持某一个序列的开头元素对另一个序列进行遍历直至匹配到相同的元素并记录。

那么如何记录找到的子序列元素以及怎么进行匹配到相同的元素后子序列的连接呢，换句话说相同的元素是可以找到的，那如何确定这些个相同元素是跟哪些组成一个子序列呢。

我们通过引入一个二维数组来解决这个问题，先引入c[i][j]来记录子序列的长度，如何找到最大的子序列长度我们通过下面的递推公式来解决：

 即当i=0，j=0时，空序列是两个序列的最长公共子序列，故此时c[i][j]=0；

当两个元素相等时，那么将在它之前的两个序列的最长子序列长度加一则得到截止到目前两个元素两个序列的子序列的长度。

当两个元素不相等时，此时的子序列长度取截止到该元素之前X序列与截止到该元素Y序列的最长子序列以及截止到该元素之前Y序列与截止到该元素X序列的最长子序列的最大值。

当遍历完成后形成的二维数组如下（X序列：ABCBDAB;Y序列：BDCABA）：

 

在我们进行这个二维数组的代码实现的时候需要自底向上对这两个序列进行遍历，并记录最优值与最优策略：

i=1时，{x1}与整个Y序列元素依次比较；

i=2时，{x2}与整个Y序列元素依次比较；

......

然后我们求出c[i][j]数组后，对数组的最后一个元素进行求值，该值就是最大子序列长度。

现在是最长子序列的长度可以求出来，那我们如何进行对于最大子序列的求解呢？

下面我们通过一张PPT图片来解释如何追踪最优解：

 也就是说我们在另外创建一个追踪子序列或者说记录相同元素来源的二维数组b[i][j]，我们在求解到最大子序列长度的过程中顺便对b[i][j]进行记录来便于我们的追踪。

 

 

代码实现如下：

 public int findLCS(){
        char[] s1=str1.toCharArray();
        char[] s2=str2.toCharArray();
        int i,j;
        for(i = 1;i <=len1;i++)//控制 s1 序列
            for(j = 1;j <=len2;j++)//控制 s2 序列
            {
                if(s1[i-1]==s2[j-1]){//如果当前字符相同，则公共子序列的长度为该字符前的最长公共序列+1
                    c[i][j] = c[i-1][j-1]+1;
                    b[i][j] = 1;
                }
                else{
                    if(c[i-1][j]>=c[i][j-1])
                    {   c[i][j] = c[i-1][j];
                        b[i][j] = 2;
                    }
                else{   c[i][j] = c[i][j-1];
                        b[i][j] = 3;
                    }
                }
            }
        return c[len1][len2];
    }

我们对于b[i][j]的求值应该是伴随着c[i][j]数组的创建的：

当c[i][j]=c[i-1][j-1]+1时，说明此时比较的X序列以及Y序列的元素相同，所以我们对于此时子序列长度值为在此元素之前的X序列以及在此元素之前的Y序列的最长子序列长度进行加一操作，说明又找到一个相同的子序列元素。所以此时对应的b[i][j]=1代表从其左上角继承的子序列值加一，对应操作为保留输出该元素并继续向左上角查找。

当c[i][j]=c[i-1][j]时，说明此时比较的X序列以及Y序列的元素不相同，所以我们对于此时子序列长度值为max（在此元素之前的X序列与包含此元素的Y序列的最长相同子序列，在此元素之前的Y序列与包含此元素的X序列的最长相同子序列），而此时c[i][j]=c[i-1][j]则说明上面的值比左面的值要大。所以此时对应的b[i][j]=2代表从其上面继承的子序列值，则不保留输出元素值，继续向上进行查找。

当c[i][j]=c[i][j-1]时，说明此时比较的X序列以及Y序列的元素不相同，所以我们对于此时子序列长度值为max（在此元素之前的X序列与包含此元素的Y序列的最长相同子序列，在此元素之前的Y序列与包含此元素的X序列的最长相同子序列），而此时c[i][j]=c[i][j-1]则说明左面的值比上面的值要大。所以此时对应的b[i][j]=3代表从其左面继承的子序列值，则不保留输出元素值，继续向左进行查找。

那么要如何输出最长子序列呢？

我们此时采用的是自底向上的输出方法：

定义一个记录输出的字符串s。

在c[i][j]先找到最长子序列的值并记录该值出现的位置，找到对应的b[i][j]的位置进行对该值判断：

b[i][j]==1，记录此时对应的X序列Y序列的元素并保存到s中；

b[i][j]==2，向上寻找，继续判断；

b[i][j]==3，向左寻找，继续判断；

上述过程用下面的图片解释一下（假设最长子序列值为4）：

有关的代码实现（通过递归来循环查找）：

public void print(int i,int j,String lcs){
        int length;
        while (i>0 && j>0){
            if (str1.charAt(i-1)==str2.charAt(j-1)){
                lcs+=str1.charAt(i-1);
                i--;
                j--;
            }
            else {
                if (c[i-1][j]>c[i][j-1])
                    i--;
                else if (c[i-1][j]>c[i][j-1])
                    j--;
                else {
                    print(i-1,j,lcs);
                    return;
                }
            }
        }
        if(lcs.length()==findLCS()) {
            for (length=findLCS()-1;length>=0;length--)
            System.out.print(lcs.charAt(length));
            System.out.println("\n");
        }
    }

 这样就输出来了最长子序列的其中一个，但是我们想要输出全部的最长子序列那要怎么实现呢？

我们首先来想一下当c[i][j-1]=c[i-1][j]时，也就是说上面跟左面的最长子序列值相等时，我们是向上查找还是向左查找呢？如果我们要全部找到最长子序列的话，那么我们左边右边都要去，这个是与输出最长子序列的其中一个不同的地方。

下面来说一下递归方法的代码实现：

public void print(int i,int j,String lcs){
        int length;
        while (i>0 && j>0){
            if (str1.charAt(i-1)==str2.charAt(j-1)){
                lcs+=str1.charAt(i-1);
                i--;
                j--;
            }
            else {
                if (c[i-1][j]>c[i][j-1])
                    i--;
                else if (c[i-1][j]>c[i][j-1])
                    j--;
                else {
                    print(i-1,j,lcs);
                    print(i,j-1,lcs);
                    return;
                }
            }
        }
        if(lcs.length()==findLCS()) {
            for (length=findLCS()-1;length>=0;length--)
            System.out.print(lcs.charAt(length));
            System.out.println("\n");
        }
    }

下面是输出两个序列的全部最长子序列的完整代码：

（1）LCS类

  1. package exp;
  2. import java.util.Scanner;
  3.  
  4. public class LCS {
  5.     private int[][] b;
  6.     private int[][] c;
  7.     private String str1;
  8.     private String str2;
  9.     private int len1;
  10.     private int len2;
  11.     public int findLCS(){
  12.         char[] s1=str1.toCharArray();
  13.         char[] s2=str2.toCharArray();
  14.         int i,j;
  15.         for(i = 1;i <=len1;i++)//控制 s1 序列
  16.             for(j = 1;j <=len2;j++)//控制 s2 序列
  17.             {
  18.                 if(s1[i-1]==s2[j-1]){//如果当前字符相同，则公共子序列的长度为该字符前的最长公共序列+1
  19.                     c[i][j] = c[i-1][j-1]+1;
  20.                     b[i][j] = 1;
  21.                 }
  22.                 else{
  23.                     if(c[i-1][j]>=c[i][j-1])
  24.                     {   c[i][j] = c[i-1][j];
  25.                         b[i][j] = 2;
  26.                     }
  27.                 else{   c[i][j] = c[i][j-1];
  28.                         b[i][j] = 3;
  29.                     }
  30.                 }
  31.             }
  32.         return c[len1][len2];
  33.     }
  34.     public void inputData(){
  35.         Scanner scanner=new Scanner(System.in);
  36.         System.out.println("请输入字符串s1：");
  37.         str1=scanner.nextLine();
  38.         System.out.println("请输入字符串s2：");
  39.         str2=scanner.nextLine();
  40.         len1=str1.length();
  41.         len2=str2.length();
  42.         c=new int[len1+1][len2+1];
  43.         b=new int[len1+1][len2+1];
  44.     }
  45.     public void print(int i,int j,String lcs){
  46.         int length;
  47.         while (i>0 && j>0){
  48.             if (str1.charAt(i-1)==str2.charAt(j-1)){
  49.                 lcs+=str1.charAt(i-1);
  50.                 i--;
  51.                 j--;
  52.             }
  53.             else {
  54.                 if (c[i-1][j]>c[i][j-1])
  55.                     i--;
  56.                 else if (c[i-1][j]>c[i][j-1])
  57.                     j--;
  58.                 else {
  59.                     print(i-1,j,lcs);
  60.                     print(i,j-1,lcs);
  61.                     return;
  62.                 }
  63.             }
  64.         }
  65.         if(lcs.length()==findLCS()) {
  66.             for (length=findLCS()-1;length>=0;length--)
  67.             System.out.print(lcs.charAt(length));
  68.             System.out.println("\n");
  69.         }
  70.     }
  71.     public void display(){
  72.         int len=findLCS();
  73.         String lcs="";
  74.         System.out.println(str1+"和"+str2+"的最长公共子序列长度是："+len);
  75.         System.out.println(str1+"和"+str2+"所有的最长公共子序列是：");
  76.         print(len1,len2,lcs);
  77.     }
  78. }

（2）Test类

  1. package exp;
  2.  
  3. public class Test {
  4.     public static void main(String[] args) {         //Input：ABCADAB，BACDBA         //Output:BADB
  5.     LCS lcs=new LCS();
  6.     lcs.inputData();
  7.     lcs.display();
  8.     }
  9. }

输出结果：

写了很长时间，表达也不是很清晰，代码更是很低级，就当做记录一下吧~ 

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/201916
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号