// Function to find length of the

// shortest supersequence of X and Y.

static int shortestSuperSequence(String X, String Y)

{

int m = X.length();

int n = Y.length();

// find lcs

int l = lcs(X, Y, m, n);

// Result is sum of input string

// lengths - length of lcs

return (m + n - l);

}

// Returns length of LCS

// for X[0..m - 1], Y[0..n - 1]

static int lcs(String X, String Y, int m, int n)

{

int[][] L = new int[m + 1][n + 1];

int i, j;

// Following steps build L[m + 1][n + 1]

// in bottom up fashion. Note that

// L[i][j] contains length of LCS

// of X[0..i - 1]and Y[0..j - 1]

for (i = 0; i <= m; i++) {

for (j = 0; j <= n; j++) {

if (i == 0 || j == 0)

L[i][j] = 0;

else if (X.charAt(i - 1) == Y.charAt(j - 1))

L[i][j] = L[i - 1][j - 1] + 1;

else

L[i][j] = Math.max(L[i - 1][j],

L[i][j - 1]);

}

}

// L[m][n] contains length of LCS

// for X[0..n - 1] and Y[0..m - 1]

return L[m][n];

}

// Driver code

public static void main(String args[])

{

String X = "AGGTAB";

String Y = "GXTXAYB";

System.out.println("Length of the shortest "

+ "supersequence is "

+ shortestSuperSequence(X, Y));

}

}