Question

1 Problem Description

Instructions.

You are provided one skeleton program named

LCS.java

. The

source files are available on Canvas in a folder named

HW6

. Please modify the

skeleton code to solve the following tasks.

•

Task 1 (100 pts). Implement the

lcs

length()

function as discussed in

Lecture 11.

•

Note:

You

should not

return the double-array

b

and

c

as in the pseu-

docode. Instead, return the length of the longest common subsequence.

•

Hint:

To get the i-th character in a string s, use

s.charAt(i)

. For example, the code

String s = ”XYZ“;

System.out.println(s.charAt(1));

prints out Y.

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"));

}

}

Answer 1

CODE

public class LCS {

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */

public static int lcs(char[] X, char[] Y, int m, int n)

{

if (m == 0 || n == 0)

return 0;

if (X[m - 1] == Y[n - 1])

return 1 + lcs(X, Y, m - 1, n - 1);

else

return Math.max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));

}

public static int lcs_length(String X, String Y) {

return lcs(X.toCharArray(), Y.toCharArray(), X.length(), Y.length());

}

public static void main(String[] args)

{

System.out.println(LCS.lcs_length("ABCBDAB", "BDCABA"));

System.out.println(LCS.lcs_length("ACCGGTCGAGTGCGCGGAAGCCGGCCGAA",

"GTCGTTCGGAATGCCGTTGCTCTGTAAA"));

}

}

OUTPUT

4