求助！求两个串的最长公共子序列（多个）

Question

想要求出两个串的最长公共子序列（不是子串，子序列可以是不连续的），以下的这个算法（用的是lcs，动态规划）能求出一个最长公共子序列，是badb，长度是4.可是这两个串bacdbd 和dbcbadb的最长公共子序列有三个，分别是badb，bcbd，bcdb，长度都是4，如何把它们都求出来？？先谢谢大家了！
import java.io.*;
public class ys
{
    static int length = 0; //保存最长公共子序列的长度
    static String  str_same = "";  //保存最长公共子序列
    static int k = 0;
    public static void main(String args[])
    {
        char x[],y[];
        String str_x="bacdbd",str_y="dbcbadb"; //原始比较的两个串
        try{
            str_x=" "+str_x;        
            str_y=" "+str_y;
        } catch(Exception e){
            e.printStackTrace();
        }
        x=str_x.toCharArray();
        y=str_y.toCharArray();
        int b[][]=new int[x.length][y.length];
        lcsLength(x,y,b);
        lcs(x.length-1,y.length-1,x,b);
        System.out.println("length:"+length);
        System.out.println("str_same:"+str_same);
        System.out.print("\n");
    }
    public  static void lcsLength(char []x,char []y,int [][]b)
    {
        int xMaxIndex=x.length-1;
        int yMaxIndex=y.length-1;
        int count[][]=new int[xMaxIndex+1][yMaxIndex+1];
        for(int i=0;i<=xMaxIndex;i++)
        {
            count[i][1]=0;
        }
        for(int i=0;i<=yMaxIndex;i++)
        {
            count[0][i]=0;
        }
        for(int i=1;i<=xMaxIndex;i++)
        for(int j=1;j<=yMaxIndex;j++)
        {
            if(x[i]==y[j]) //如果相等 则对角线加一
            {
                count[i][j]=count[i-1][j-1]+1;
                b[i][j]=1;
            }
            //如果不等,则比较上方和左方,取最大值
            else if(count[i-1][j]>=count[i][j-1]) 
            {
                count[i][j]=count[i-1][j];
                b[i][j]=2;
            }
            else 
            {
                count[i][j]=count[i][j-1];
                b[i][j]=3;
            }
            
        }
    }
    public static void lcs(int i,int j,char []x,int [][]b)
    {
        if(i==0||j==0)
        {
            return;
        }
        if(b[i][j]==1)
        {
            length ++;           
            lcs(i-1,j-1,x,b);
            str_same += x[i];
        }
        else if(b[i][j]==2)
        {
            
            lcs(i-1,j,x,b);
            
        }
        else if(b[i][j]==3)
        {
            lcs(i,j-1,x,b);
        }
    }
}

Answer 1

import java.io.*;
public class Ys
{
    static int length = 0; //保存最长公共子序列的长度
    static int maxLength = 0;//记录最长子序列长度
    static int count = 0;
    
    static int k = 0;
    public static void main(String args[])
    {
     String  str_same = "";  //保存最长公共子序列
        char x[],y[];
        String str_x="bacdbd",str_y="dbcbadb"; //原始比较的两个串
        try{
            str_x=" "+str_x;        
            str_y=" "+str_y;
        } catch(Exception e){
            e.printStackTrace();
        }
        x=str_x.toCharArray();
        y=str_y.toCharArray();
        int b[][]=new int[x.length][y.length];
        lcsLength(x,y,b);
        lcs(x.length-1,y.length-1,x,b,"");
        /*
        System.out.println("length:"+length);
        System.out.println("str_same:"+str_same);
        System.out.print("\n");
        */
    }
    public  static void lcsLength(char []x,char []y,int [][]b)
    {
        int xMaxIndex=x.length-1;
        int yMaxIndex=y.length-1;
        int count[][]=new int[xMaxIndex+1][yMaxIndex+1];
        for(int i=0;i<=xMaxIndex;i++)
        {
            count[i][1]=0;
        }
        for(int i=0;i<=yMaxIndex;i++)
        {
            count[0][i]=0;
        }
        for(int i=1;i<=xMaxIndex;i++)
        for(int j=1;j<=yMaxIndex;j++)
        {
            if(x[i]==y[j]) //如果相等 则对角线加一
            {
                count[i][j]=count[i-1][j-1]+1;
                maxLength = Math.max(maxLength,count[i][j]);
                b[i][j]=1;
            }
            //如果不等,则比较上方和左方,取最大值
            else if(count[i-1][j]>=count[i][j-1]) 
            {
                count[i][j]=count[i-1][j];
                maxLength = Math.max(maxLength,count[i][j]);
                b[i][j]=2;
            }
            else 
            {
                count[i][j]=count[i][j-1];
                maxLength = Math.max(maxLength,count[i][j]);
                b[i][j]=3;
            }
            
        }
    }
    public static void lcs(int i,int j,char []x,int [][]b,String strResult)
    {
        if(i==0||j==0)
        {
            return;
        }
        if(b[i][j]==1)
        {
         strResult = x[i] + strResult;
         if (strResult.length() == maxLength) {
         System.out.println(strResult.length());
         System.out.println(strResult);
         }
        
            length ++;           
            lcs(i-1,j-1,x,b,strResult);
            //str_same += x[i];
        }
        else
        {
         lcs(i-1,j,x,b,strResult);
         lcs(i,j-1,x,b,strResult);
        }
        /*
        else if(b[i][j]==2)
        {
            
            lcs(i-1,j,x,b);
            
        }
        else if(b[i][j]==3)
        {
            lcs(i,j-1,x,b);
        }
        */
    }
}在你的基础上做了部分修改，能得出你要的结果，没有深入测试

Answer 2

解释下
原程序不能输出全部的结果的原因是
我在注释掉的部分
 /* 
        else if(b[i][j]==2) 
        { 
             
            lcs(i-1,j,x,b); 
             
        } 
        else if(b[i][j]==3) 
        { 
            lcs(i,j-1,x,b); 
        } 
        */ 
引起的。
如果b[i][j]是 2 或者 3 的话
原程序没有实现完全遍历，因为 lcs（动态规划）算法目的是输出一个子序列，不是全部。
代码仍有可以改进的地方，例如退出递归的条件。