package shortestCommonSupersequence;

public class ShortestCommonSupersequence {

// returns shortest supersequence of X and Y

static String printShortestSuperSeq(String X, String Y)

{

int m = X.length();

int n = Y.length();

// dp[i][j] contains length of

// shortest supersequence

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

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

// Fill table in bottom up manner

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

{

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

{

// Below steps follow recurrence relation

if (i == 0)

{

dp[i][j] = j;

}

else if (j == 0)

{

dp[i][j] = i;

}

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

{

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

}

else

{

dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);

}

}

}

// Following code is used to print

// shortest supersequence dp[m][n] s

// tores the length of the shortest

// supersequence of X and Y

int index = dp[m][n];

// string to store the shortest supersequence

String str = "";

// Start from the bottom right corner and one by one

// push characters in output string

int i = m, j = n;

while (i > 0 && j > 0)

{

// If current character in X and Y are same, then

// current character is part of shortest supersequence

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

{

// Put current character in result

str += (X.charAt(i - 1));

// reduce values of i, j and index

i--;

j--;

index--;

}

// If current character in X and Y are different

else if (dp[i - 1][j] > dp[i][j - 1])

{

// Put current character of Y in result

str += (Y.charAt(j - 1));

// reduce values of j and index

j--;

index--;

}

else

{

// Put current character of X in result

str += (X.charAt(i - 1));

// reduce values of i and index

i--;

index--;

}

}

// If Y reaches its end, put remaining characters

// of X in the result string

while (i > 0)

{

str += (X.charAt(i - 1));

i--;

index--;

}

// If X reaches its end, put remaining characters

// of Y in the result string

while (j > 0)

{

str += (Y.charAt(j - 1));

j--;

index--;

}

// reverse the string and return it

str = reverse(str);

return str;

}

static String reverse(String input)

{

char[] temparray = input.toCharArray();

int left, right = 0;

right = temparray.length - 1;

for (left = 0; left < right; left++, right--)

{

// Swap values of left and right

char temp = temparray[left];

temparray[left] = temparray[right];

temparray[right] = temp;

}

return String.valueOf(temparray);

}

// Driver code

public static void main(String[] args)

{

String X = "geeke";

String Y = "eke";

System.out.println(printShortestSuperSeq(X, Y));

}

}