My code:
static void LCS(String x, String y){
int m = x.length();
int n = y.length();
int len[][] = new int[m+1][n+1]; // by default init. to zeros
int b[][] = new int[m+1][n+1]; // by default init. to zeros
for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
if(i==0 || j==0){
len[i][j] = 0;
}
else{
if(x.charAt(i-1)==y.charAt(j- 1)){
len[i][j] = len[i-1][j-1] + 1;
b[i][j] = -2;
}
else{
if(len[i][j-1]>len[i-1][j]){
len[i][j] = len[i][j-1];
b[i][j] = -3;
}else{
len[i][j] = len[i-1][j];
b[i][j] = -1;
}
}
}
}
}
System.out.println("length of LCS " + len[m][n]);
int i=m,j=n;
String res= "";
while(true){
if(b[i][j] == -1){
i--;
}
if(b[i][j] == -2){
res = x.charAt(i-1)+ res;
i--;j--;
}
if(b[i][j] == -3){
j--;
}
if(res.length()==len[m][n])
break;
}
System.out.println("LCS " + res);
}
static void LCS(String x, String y){
int m = x.length();
int n = y.length();
int len[][] = new int[m+1][n+1]; // by default init. to zeros
int b[][] = new int[m+1][n+1]; // by default init. to zeros
for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
if(i==0 || j==0){
len[i][j] = 0;
}
else{
if(x.charAt(i-1)==y.charAt(j-
len[i][j] = len[i-1][j-1] + 1;
b[i][j] = -2;
}
else{
if(len[i][j-1]>len[i-1][j]){
len[i][j] = len[i][j-1];
b[i][j] = -3;
}else{
len[i][j] = len[i-1][j];
b[i][j] = -1;
}
}
}
}
}
System.out.println("length of LCS " + len[m][n]);
int i=m,j=n;
String res= "";
while(true){
if(b[i][j] == -1){
i--;
}
if(b[i][j] == -2){
res = x.charAt(i-1)+ res;
i--;j--;
}
if(b[i][j] == -3){
j--;
}
if(res.length()==len[m][n])
break;
}
System.out.println("LCS " + res);
}
No comments:
Post a Comment