最长公共子printdDiff [英] longest common subsequence printdDiff
本文介绍了最长公共子printdDiff的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
有关最长公共子序列算法只是一个简单的问题。 我这样做,你需要生成序列的部分如下:
Just a quick question about the longest Common subsequence algorithm. I have done the part where you need to generate the subsequence as follow:
public int[][] lcsLength(char[] input1, char[] input2) {
int[][] opt = new int[M][N];
for (int i = 1; i < input1.length; i++) {
for (int j = 1; j < input2.length; j++) {
if (input1[i] == input2[j]) {
opt[i][j] = opt[i - 1][j - 1] + 1;
} else {
opt[i][j] = Math.max(opt[i][j - 1], opt[i - 1][j]);
}
}
}
return opt;
}
和printDiff功能如下:
and the printDiff function as follow:
private static void printDiff(int[][] opt,String x,String y,int i, int j) {
if(i>0 &&j>0 && x.charAt(i-1)==y.charAt(j-1)){
printDiff(i-1,j-1);
System.out.println(x.charAt(i-1));
}
else{
if(j>0&&(i==0||opt[i][j-1]>=opt[i-1][j])){
printDiff(i-1,j-1);
System.out.println("-"+y.charAt(j-1));
}
else if(i>0&&(j==0|| opt[i][j-1]<=opt[i-1][j])){
printDiff(i-1,j-1);
System.out.println(x.charAt(i-1));
}
}
}
然后,如果我用这个作为参数:
And then if I use this as parameters:
String input1="ABCDE"
String input2="ACDC"
int i=input1.length()
int j=input2.length()
产生选择矩阵lcsLength()后,我想,竟被printdiff给我:
after generating the opt matrix with lcsLength() I wish that printdiff woul give me :
ABCDE-
A-CD-C
而是我得到的:
but instead I get:
ABCDE-
ABCD-C
这是我做错了什么会帮助我很多的任何想法
any ideas on what I did wrong would help me a lot
谢谢 洛朗
推荐答案
不知道,如果它是一个相关的问题,但我觉得你的LCS code应该是:
Don't know if it's a related issue, but I think your LCS code should be:
public int[][] lcsLength(char[] input1, char[] input2) {
int[][] opt = new int[input1.length+1][input2.length+1];
for (int i = 1; i <= input1.length; i++) {
for (int j = 1; j <= input2.length; j++) {
if (input1[i-1] == input2[j-1]) {
opt[i][j] = opt[i - 1][j - 1] + 1;
} else {
opt[i][j] = Math.max(opt[i][j - 1], opt[i - 1][j]);
}
}
}
return opt;
}
这篇关于最长公共子printdDiff的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文