print_scs.java

public class print_scs {
        public String shortestCommonSupersequence(String str1, String str2) {
            int[][] dp = new int[str1.length() +1][str2.length()+1];

            for(int i = 0; i <= str1.length(); i++) {
                for(int j = 0; j <= str2.length(); j++) {
                    if(i == 0 || j == 0) dp[i][j] = 0;
                    else if(str1.charAt(i-1) == str2.charAt(j-1)) {
                        dp[i][j] = 1 + dp[i-1][j-1];
                    } else {
                        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                    }
                }
            }

            int i = str1.length();
            int j = str2.length();
            StringBuffer result = new StringBuffer();

            while(i > 0 && j > 0) {
                if (str1.charAt(i-1) == str2.charAt(j-1)) {
                    result.append(str1.charAt(i-1));   // print lcs variation
                    i--;
                    j--;
                } else if( dp[i-1][j] > dp[i][j-1] ) {
                    result.append(str1.charAt(i-1));  // lcs variation
                    i--;
                } else {
                    result.append(str2.charAt(j-1)); // variation
                    j--;
                }
            }


            // after adding common i.e lcs we are adding rest of them also

            while(i > 0) {
                result.append(str1.charAt(i-1));
                i--;
            }


            while(j > 0) {
                result.append(str2.charAt(j-1));
                j--;
            }

            return result.reverse().toString();
        }
    }