想要求出两个串的最长公共子序列(不是子串,子序列可以是不连续的),以下的这个算法(用的是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);
}
}
}
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);
}
}
}
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);
}
*/
}
}在你的基础上做了部分修改,能得出你要的结果,没有深入测试
原程序不能输出全部的结果的原因是
我在注释掉的部分
/*
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(动态规划)算法目的是输出一个子序列,不是全部。
代码仍有可以改进的地方,例如退出递归的条件。