求助！求两个串的最长公共子序列
想要求出两个串的最长公共子序列（不是子串，子序列可以是不连续的），以下的这个算法（用的是lcs，动态规划）能求出一个最长公共子序列，是badb，长度是4.可是这两个串bacdbd 和dbcbadb的最长公共子序列有三个，分别是badb，bcbd，bcdb，长度都是4，如何把它们都求出来？？先谢谢大家了！[code]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);
}
}
}[/code]
页:
[1]