Question

Write the pseudo code for longest common subsequence algorithm in Java.

Alg lCS( X , n, Y, m)

Input: String X of length n, String Y of length m

Output: return the length of the longest common subsequence between X and Y

Answer 1

Answer:

class Main {

/*return the length of the longest common subsequence between X and Y */

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

{

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

return 0;

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

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

else

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

}

/* Utility function to get max of 2 integers */

int max(int a, int b)

{

return (a > b) ? a : b;

}

public static void main(String[] args)

{

Main lcs = new Main();

String s1 = "AGGTAB";

String s2 = "GXTXAYB";

char[] X = s1.toCharArray();

char[] Y = s2.toCharArray();

int n = X.length;

int m = Y.length;

System.out.println("Length of LCS is"+ " " + lcs.lcs(X, n, Y, m));

}

}

Output:

Please give thumbsup, if you like it. Thanks.