******************************* package dp; public class LCS { public static int
ID: 3600645 • Letter: #
Question
*******************************
package dp;
public class LCS {
public static int lcs_length (String X, String Y) {
/*
* fill in your code here
* Note: return the length of LCS, instead of c and b
*/
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(LCS.lcs_length("ABCBDAB", "BDCABA"));
System.out.println(LCS.lcs_length("ACCGGTCGAGTGCGCGGAAGCCGGCCGAA", "GTCGTTCGGAATGCCGTTGCTCTGTAAA"));
}
}
Implement the lcs_length() functionExplanation / Answer
package dp;
public class LCS {
public static int lcs_length (String x, String y)
{
int ls1 = x.length();
int ls2 = y.length();
int[][] a = new int[ls1 + 1][ls2 + 1];
for (int i = ls1 - 1; i >= 0; i--)
{
for (int j = ls2 - 1; j >= 0; j--)
{
if (str1.charAt(i) == str2.charAt(j))
a[i][j] = a[i + 1][j + 1] + 1;
else
a[i][j] = Math.max(a[i + 1][j], a[i][j + 1]);
}
}
int i = 0, j = 0;
StringBuffer s = new StringBuffer();
while (i < ls1 && j < ls2)
{
if (str1.charAt(i) == str2.charAt(j))
{
s.append(str1.charAt(i));
i++;
j++;
}
else if (a[i + 1][j] >= a[i][j + 1])
i++;
else
j++;
}
String s1 = s.toString();
return s1.length();
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(LCS.lcs_length("ABCBDAB", "BDCABA"));
System.out.println(LCS.lcs_length("ACCGGTCGAGTGCGCGGAAGCCGGCCGAA", "GTCGTTCGGAATGCCGTTGCTCTGTAAA"));
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.